[数据结构与算法]数据结构之【绪论】

一、 概述

• 算法 + 数据结构 = 程序
  • 程序： 计算机指令的 组合。
  • 算法：程序的逻辑抽象。
  • 数据结构：数据极其关系的反应，从逻辑结构和存储（物理）结构。
• 数据结构解决具体问题 ：
  • 1、数据的逻辑结构
  • 2、数据的存储结构
  • 3、数据操作和运算

二、数据与数据结构

2.1 术语

• 数据（Data）：数据是信息的载体，是对客观事务的符号表示。
• 数据元素（Data Element）：是数据的基本单位，是一个个体。相当于表的一行。
• 数据项（Data Item）： 是数据元素的组成部分。相当于表的列。
• 数据对象（Data Object）：性质相同的数据元素的集合。相当于表。
• 数据结构（Data Structure）：特定关系的数据元素的集合。

2.2 逻辑结构

• 数据元素之间的逻辑关系，与存储数据无关。独立于计算机之外。
• 数据元素的特性 ：
  • 1、集合：元素之间没有关系比较松散。
  • 2、线性结构：元素之间存在 一对一 关系。除了开始和终端结点。其他节点有一个前驱和一个后继。
  • 3、树形结构：元素之间存在 一对多 关系。
  • 4、图形结构：元素之间存在 多对多 关系。
• 数据的逻辑结构需要 2 部分：数据元素（Data）、数据元素的关系（relationship）
  

2.3 存储结构

• 数据的存储结构，也称为物理结构，是数据的逻辑结构在计算机的实现。
  • 数据元素的值存储表示和逻辑关系
• 存储结构的 4 种方式：
  • 1、顺序存储：在一片连续的存储空间中进行存储，元素的逻辑位置和物理位置保持一致。例如：数组
    
  • 2、链式存储：可以存储在任意的物理物质上，需要额外的部分存放逻辑关系的指针。如：链表
    
  • 3、索引存储：存储数据的同时，额外存储一个索引表。在查询时可以提高效率。
  • 4、散列存储：一般情况物理上是可以连续的存储空间，需要通过 散列函数hash 来确定存储位置。在查询时可以提高效率
    

2.4 数据操作

• 初始化：创建、销毁
• 数据操作：插入 | 添加、删除、修改
• 数据使用：查找、遍历

三、 算法

3.1 概述

• 对特定问题求解步骤的一种描述。是指令的有限序列

3.2 算法特性

• 1、有穷性：有限
• 2、确定性：需求确定、指令确定
• 3、有效性：指令都是有意义
• 4、输入
• 5、输出
  

3.3 算法目标

• 1、真确性：基本要求，需求和实现对应
• 2、可读性：是程序员能够读懂，编写代码时可以辅助注释
• 3、健壮性：临界值的处理、无效数据的校验等
• 4、高效性：使用较少的资源（时间资源、空间资源）。一个好的算法要做到执行时所需时间尽量简短，所需的最大存储空间尽量少

3.4 算法分析：概述

• 算法的复杂度是衡量算法优劣的重要依据
• 算法的复杂度分类：时间复杂度、空间复杂度
• 时间复杂度：执行时间的长短
• 空间复杂度：执行时空间需求量，也就是计算机资源的使用量

3.5 算法分析：时间复杂度

• 主要考虑因素：

  • 1、算法本身
  • 2、问题规模
  • 3、程序语言选择
  • 4、编译程序（JDK优劣）
  • 5、硬件速度
  • 6、运行软件

• 时间复杂度通过 大O表示法 进行表示，大O表达式只需要考虑最高次幂的项

  • 常量阶：O(1)
  • 线性阶：O(n)
  • 平方阶：O(n^2)
  • 立方阶：O(n^3)
  • 对数阶：O(log2n)
  • 线对数阶：O(nlog2n)
  • O(log2n) 指数计算：R表示次数
  • O(n) : 一层循环
  • O(n^2)：二层循环（99乘法表）
  • O(n^3)：三层循环

• 时间复杂度
  
  

• 计算公式
  

四、西格玛Σ求和

4.1 计算方式

• 示例