0x01：什么是数据结构

一、数据结构

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素），以及它们之间的关系和运算等相关问题的学科；而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

• 数据（DATA）

  • 对信息的一种符号表示，在计算机学科中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

• 数据元素（DATA Element）

  • 数据的基本单位，在程序中通常作为一个整体进行考虑和处理
  • 一个数据元素可由若干个数据项所组成
  • 数据项是数据不可分割的最小单位

• 数据结构（DATA Structure）

  • 互相之间存在一种或多种特定关系的数据元素的集合
  • 数据结构是带“结构”的数据元素的集合，”结构“就是指数据元素之间存在的关系

• 数据类型（Data Type）

  • 在一种程序设计语言中，变量所具有的数据种类

例如在C语言中，基本数据类型有：char、int、float、double、void；构造数据类型有：数组、结构体、共用体、文件；

• 抽象数据类型（Abstract Data Type）

  • 指一个数学模型以及定义在此数学模型上的一组操作，即把数据类型和数据类型上的运算捆绑在一起，进行封装

    • 更高层次的数据抽象
    • 由用户定义，用以表示应用问题的数据模型
    • 由基本的数据类型组成，并包括一组相关操作
  • 最常用的数据运算有五种，分别为插入、删除、修改、查找、排序

二、逻辑结构和物理结构

• 逻辑结构
  数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，它是从具体问题抽象出来的数学模型；从逻辑结构上分，数据结构可以归结为以下四类：

  • 线性结构
    线性结构中的数据元素之间是一对一关系，例如线性表、栈、队列

  

  • 树形结构
    树形结构的数据元素之间存在一种一对多的层次关系，例如树

  

  • 图状结构
    图形结构的数据元素是多对多的关系，例如图

  

  • 集合结构
    数据元素间除“同属于一个集合”外，无其它关系

  

• 存储结构（物理结构）
  数据元素及其关系在计算机存储器中的存储方式

从存储结构上分，数据结构可以归结为以下四类：

• 顺序存储结构
  借助元素在存储器中相对位置来表示数据元素之间的逻辑关系；即把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
  
• 链式存储结构
  借助指示元素存储地址的指针表示数据元素之间的逻辑关系；特点是元素在物理上可以不相邻，但每个数据元素包括了一个数据域和一个指针域
  
• 索引存储结构
  除数据元素存储在地址连续的内存空间以外，还需建立一个索引表，兼有静态和动态的特性
• 散列存储结构
  通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将散列函数的值解释成关键字所在元素的存储地址。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取

0x02：算法

一、什么是算法

N·沃思（Niklaus Wirth）教授提出：程序 = 算法 + 数据结构；
算法就是计算或者解决问题的步骤；在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。
简单来说，算法就是程序解决问题的方法

二、算法的特性

算法具有五个基本特征：输入、输出、有穷性、确定性和可行性

• 输入

  • 算法具有零个或者多个输入

• 输出

  • 算法至少有一个或多个输出
  • 算法是一定要有输出的，输出的形式可以是打印形式输出，也可以是返回一个或者多个值等

• 有穷性

  • 有穷性是指在执行有限次步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成

• 确定性

  • 算法的每一个步骤具有确定的含义，而不会出现二义性
  • 算法在一定条件下，只有一条执行路径，相同的输入只能有唯一的输出结果
  • 算法的每个步骤都应该被精确定义而无歧义

• 可行性

  • 算法的每一步都必须是可行的；也就是说，每一步都能通过执行有限次数完成

三、算法设计的要求

• 正确性
  正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够的得到问题的正确答案；大体分为以下四个层次：

  • 算法程序没有语法错误
  • 算法程序对合法输入能够产生满足要求的输出
  • 算法程序对非法输入能够产生满足规格的说明
  • 算法程序对于故意刁难的测试输入都有满足要求的输出结果
• 可读性
  算法设计的另一目的是为了便于阅读、理解和交流
• 健壮性
  当输入数据不合法时，算法也能做出对应的处理，而不是抛出异常、崩溃或输出莫名其妙的结果
• 高效性
  高效的算法应该具备时间效率高和存储量低的特点

四、算法的设计模式

在算法设计中一些常见的通用想法可以称为算法设计模式。常见模式包括：

• 枚举法
  根据具体问题枚举出各种可能，从中选出有用信息或者问题的解。这种方法利用计算机的速度优势，在解决简单问题时非常有效。
• 贪心法
  如前面所说，根据问题的信息尽可能做出部分的解，并基于部分解逐步扩充得到完整的解。在解决复杂问题时，这种做法未必能得到最好的解
• 分治法
  把复杂问题分解为相对简单的子问题，分别求解，最后通过组合起子问题的解的方式得到原问题的解
• 回溯法（搜索法）
  专指通过探索的方式求解。如果问题很复杂，没有清晰的求解路径，可能就需要分步骤进行，而每一步骤又可能有多种选择。在这种情况下，只能采用试探的方式，根据实际情况选择一个可能的方向。当后面的求解步骤无法继续时，就需要退回到前面的步骤，另行选择求解路径，这种动作称为回溯
• 动态规划法
  在一些复杂情况下，问题求解很难直截了当地进行，因此需要在前面的步骤中积累信息，在后续步骤中根据已知信息，动态选择已知的最好求解路径（同时可能进一步积累信息）。这种算法模式被称为动态规划
• 分支限界法
  可以看作搜索方法的一种改良模式。如果在搜索过程中可以得到一些信息，确定某些可能的选择实际上并不真正有用，就可以及早将其删除，以缩小可能的求解空间，加速问题求解过程

五、算法效率的度量方法

算法的效率可以通过时间和空间来进行度量，即时间复杂度和空间复杂度

时间复杂度

假如，随着问题规模n的增长，算法执行时间的增长率和$ f(n) $的增长率相同，则可记作：

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

称$ T(n) $为算法的（渐近）时间复杂度，简称时间复杂度

$$ 算法 = 控制结构 + 原操作（固有数据类型的操作） $$

$$ 算法的执行时间 = 原操作（i）的执行次数 * 原操作（i）的执行时间 $$

也就是说，算法的执行时间与原操作执行次数之和成正比；

故，从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。

• 推导大O阶法

  • 用常数1取代运行时间中的所有加法常数
  • 在修改后的运行次数函数中，只保留最高阶项
  • 如果最高阶存在且不为1，则去除与这个项相乘的常数
    经过以上操作得到的最后结果就是大O阶

• 常数阶

  {
      ++x;s=0;
  }

  • 将x自增看成是基本操作，则语句频度为1，即时间复杂度为O(1)
  • 如果将s=0也看成是基本操作，则语句频度为2，其时间复杂度仍为O(1)，即常数阶

• 线性阶
  一般含有非嵌套循环涉及线性阶，线性阶就是随着问题规模n的扩大，对应计算次数呈直线增长

  for(i=1;i<=n;++i){
      ++x;
      s+=x;
  }

  • 语句频度为2n
  • 时间复杂度为O(n)，即时间复杂度为线性阶

• 对数阶

  void f(int n){
      int x=1;
      while(x<n){
          x=2*x;
      }
  }

  • 基本语句是x=2*x，设其执行时间为T(n)，则有2^T(n)≤n，即T(n)＜log₂n=O(log₂n)
  • 其时间复杂度为：O(log₂n)，即时间复杂度为对数阶

• 平方阶

  for(i=1;i<=n;++i){
      for(j=1;j<=n;++j){
          ++x;
          s+=x;
      }
  }

  • 语句频度为：2n²
  • 其时间复杂度为：O(n²)
  • 当n等于100，也就是说外层循环每执行一次，内层循环就执行100次，那么总共程序想要从这俩个循环跳出，就需要执行100*100次，也就是n的平方。故这段代码的时间复杂度为O(n²)。即时间复杂度为平方阶

• 立方阶

  for(i=1;i<=n;++i){
      for(j=1;j<=n;++j){
          c[i][j]=0;
          for(k=1;k<=n;++k){
              c[i][j]+=a[i][k]*b[k][j];
          }
      }
  }

  • 这是一个三重循环，每次循环从1到n，则总次数为n * n * n = n³；故时间复杂度为T(n)=O(n³)，是立方阶

空间复杂度

假如随着问题规模$ n $的增大，算法运行所需存储的增长率与$ g(n) $的增长率相同，可记作：

$$ S(n)=O(g(n)) $$

称$ S(n) $为算法的空间复杂度

• 算法的存储量包括

  1. 输入数据所占的空间
  2. 程序本身所占的空间
  3. 辅助变量所占的空间
• 若输入数据所占空间只取决于问题本身，与算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间
• 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作
• 若所需存储量依赖于特定的输入，则通常按最坏情况考虑

对于算法的分析

• 一种方法是计算所有情况的平均值，这种方法称为平均时间复杂度
  平均运行时间是所有情况中最有意义的，因为它是期望的运行时间。可现实中，平均运行时间很难通过分析得到，一般都是通过运行一定次数的实验数据后估算出来的。
• 另一种方法是计算最坏情况下的时间复杂度，这种方法称为最坏时间复杂度。
  最坏运行时间是一种保证，那就是运行时间将不会再坏了。

一般在没有特殊说明的情况下，都是指最坏时间复杂度

• 多项式时间的关系为：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³)
• 指数时间的关系为：O(2ⁿ) < O(n!) < O(nⁿ)