数据结构之绪论

---

数据结构——知识架构

什么是数据？

• 是信息的载体，是可以让计算机识别的并处理的符号集合，从底层来说就是一些二进制的0和1。

数据元素与数据项

• 数据的基本单位就是数据元素，多个数据项构成一个数据元素，数据项是数据元素的最小表示单位

• 但对于现实世界中，评判什么是数据元素与数据项，需要根据具体需求来定义。例如，对于一个学生管理系统，每一个学生的账号就是一个数据元素，而每个学生的性别、年龄、爱好等个人信息就是一个个的数据项，这些数据项构成了学生这个数据元素。

数据结构与数据对象

• 数据结构是相互具有一种或多种特定关系的数据元素的集合

• 数据对象时具有==相同性质==的数据元素的集合，是数据的子集

数据的逻辑结构

集合

• 每个元素同属于一个集合

线性结构

• 每个线性结构中只有一个前驱结点，线性结构中的每个数据元素（除了最后一个元素外）都只有唯一的后继结点，相互之间是一对一的关系

树形结构

• 每个树形结构都有一个根结点，每个子节点都只有唯一的父节点，而每个父节点不止一个子节点，相互之间是一对多的关系

图（网）结构

• 各个数据元素间都有一定的关系，相互之间是多对多的关系

数据的物理结构

顺序存储

• 即逻辑上连续的数据元素在物理内存空间内也必须是连续的内存地址空间来进行存储，元素之间的关系由存储结构的邻接关系所体现

链式存储

• 在逻辑上相邻的元素可以在物理的存储空间中不相邻，只要用指针来表示各个元素间的逻辑关系即可

索引存储

• 在内存存储数据元素的同时，再创建索引表通过索引表内的索引项指向内存中的数据元素，形成某种相互关系

散列存储

• 根据元素关键字直接计算出该元素所在内存的地址值，又称哈希（hash）存储

数据的运算

• 数据的运算包括数据的定义与实现，定义偏向于逻辑层面，即针对运算的功能；而实现偏向于物理层面，即针对运算的具体步骤

数据类型

• 一个值的集合和定义此集合的一组操作的总称
• 分为原子类型和结构类型：
  • 原子类型：即不可再分的数据类型，例如int
  • 结构类型：其值可以分成若干部分，如一个方法中的各成员变量

抽象数据类型

• 用数学化的语言定义的数据逻辑结构

算法——知识架构

什么是算法？

• 程序$=$数据结构$+$算法
• 数据结构：即把需求写入计算机中，用计算机可以理解的语言来把需求的信息存进计算机中，并对其结构进行操作
• 算法：解决需求的一种方案或方法，处理信息

算法的特性

• 有穷性
  • 算法是有穷的，但程序时无穷的
  • 算法不可以是无限循环，这样的算法是死的，并且在有穷的时间内完成
• 确定性
  • 算法中的每条指令都是有意义的，输入同样的信息必须输出相同的结果
• 可行性
  • 可通过已经实现的有限次运算步骤中实现
• 有输入
  • 一个算法必要要有0或多个输入，数量取决于需求
• 有输出
  • 一个算法必须要有一个或多个输出，不然会死循环！

好的算法的特点

• 正确性

  • 必须得出正确的结果

• 可读性

  • 可以让人们很好的理解算法的实现

• 健壮性

  • 输入错误数据时，不会输出莫名其妙的数据，而是通过判断来检测出输入数据的正误

• 高效率与低内存

  • 即执行速度快，时间复杂度低

算法效率的度量

时间复杂度

• 事前预估算法时间开销$T(n)$与问题规模$n$的关系
• 它是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 $n_0$ 大）的输入，它至多需要 $5n^3 + 3n$ 的时间运行完毕，那么它的渐近时间复杂度是 O($n^3$)。(摘自Wikipedia)

时间复杂度公式 (算法的渐进时间复杂度)

$$T(n)=O(f(n))$$

• 其中$f(n)$ 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：==算法的渐进时间复杂度==。

• 例如：

   for(int i = 0;i <= n;i++){
       int j = i;
       j++;
   }
  

  • 假设每行代码的执行时间都是一样的，我们用$1$颗粒时间 来表示，那么这个例子的第一行耗时是1个颗粒时间，第三行的执行时间是 n个颗粒时间，第四行的执行时间也是 n个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ，即 (1+2n)个颗粒时间，即： $T(n) = (1+2n)颗粒时间$，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)

• 常见的时间复杂度量级有：

  • 常数阶 $O(1)$
  • 对数阶 $O(logN)$
  • 线性阶 $O(n)$
  • 线性对数阶 $O(nlogN)$
  • 平方阶 $O(n^2)$
  • 立方阶 $O(n^3)$
  • K次方阶 $O(n^k)$
  • 指数阶 $(2^n)$

时间复杂度运算

• 加法规则

  $$T(n) = T_1(n) + T_2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))$$
  • 多项相加，只保留最高阶的项，且系数变为1

• 乘法规则

  $$T(n) = T_1(n)×T_2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))$$
  • 多项相乘，全部保留

• 各常见时间复杂度关系

  $$O(1)<O(log_2 n)<O(n)<O(n log_2 n)<O(n^2)<O(2^n)<O(n!)<O(n^n)$$

• 最坏时间复杂度:

  • 最坏情况下算法的时间复杂度

• 平均时间复杂度:

  • 所有输入示例等概率出现的情况下,算法的期望运行时间

• 最好时间复杂度:

  • 最好情况下算法的时间复杂度

空间复杂度

• 无论问题规模怎么变,算法运行所需的内存空间，都是固定的常量,算法空间复杂度为

  $$S(n) = O(1)$$

  注:S表示 “Space”
  算法原地工作——算法所需内存空间为常量

• 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，因此我们用 S(n) 来定义。

• $S(n)=O(n)$

   void arr(int n){
       int arr1[n];
       int i;
   }
  

  • 假设一个int类型占4B，则上面的代码占用的内存为：

    $$S(n)=4+4n+4$$

  • i变量占4B，n变量占4B，数组 arr[n],占4n

• $S(n)=O(n^2)$

   void one_arr(int n){
       int arr2[n][n];
       int i;
   }
  

  • 此时上面的代码占用的内存为：

    $$S(n)=n^2+4$$
    

  • 简记为：$S(n)=O(n^2)$

• $S(n)=O(n^2)+O(n)+O(1)$

   void one_arr1(int n){
       int arr2[n][n];
       int arr[n]
       int i;
   }
  

  • 此时上面的代码占用的内存为：

    $$S(n)=O(n^2)+O(n)+O(1)=O(n^2)$$
    • 只保留最高指数项

参考资料：https://zhuanlan.zhihu.com/p/50479555

简书：https://www.jianshu.com/p/f4cca5ce055a