01 基本概念

01-基本概念

什么是数据结构

关于数据的组织

数据结构（Data Structure）：计算机存储、组织数据的方式。

精心选择的合适的数据结构可以带来最优效率的算法。

由此可见评价一个数据结构使用的一个标准就是操作数据结构的算法的效率如何。

在书架的例子中，需要解决的问题有：

1. 新书怎么插入
2. 怎么找到某本指定的书

方案一：随机插入书籍。这种方式的插入十分简单，但是查找很困难。

方案二：按照首字母排序。这种方式容易查找（二分法），但是如果插入首字母为 A 的书籍，需要将大量的书籍向后移动才可以插入。

方案三：方案二的基础上进行预留空间、分类摆放。这样可以缩小每一块区域的数据量，便于查找和放置。此时又有了新的问题：预留空间的大小如何设定、分类的粗细如何确定等。

“解决问题的效率，和数据的组织方式是直接相关的。”

关于空间的使用

例子：写程序实现一个函数 printN，使得传入一个正整数为 N 的参数后，能顺序打印从 1 到 N 的全部正整数。

两种实现思路：

1. 循环
2. 递归

注意！递归的代码虽然可能简洁易懂，但是对于空间的占用十分恐怖，很容易因为占用空间过大而导致程序非正常终止。

“解决问题方法的效率，跟空间的利用效率有关。”

关于算法的效率

例子：写程序计算给定多项式在定点 \(x\) 处的值

\[ f(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1} + a_nx^n \]

两种实现：

1. 使用原式循环求和

   double f(int n, double a[], double x)
   {
       int i;
       double p = a[0];
       for (i = 1; i <= n; i++)
           p += (a[i] * pow(x, i));
       return p;
   }
   

2. 使用下式求和

   \[ f(x) = a_0 + x(a_1 + x(a_2 + \cdots + x(a_{n-1} + x a_n)\cdots)) \]

   double f(int n, double a[], double x)
   {
       int i;
       double p = a[n];
       for (i = n; i > 0; i--)
           p = a[i-1] + x * p;
       return p;
   }
   

上面两种解法都能实现算法，但是效率不同。明显第二种效率高于第一种。分析知二的时间复杂度为 \(O(n)\)，而一的时间复杂度为 \(O(n^2)\)，因为 pow(x, i) 的实现的时间复杂度通常也是 \(O(n)\)。

“解决问题方法的效率，跟算法的巧妙程度有关。”

总结什么是数据结构

解释

数据结构与算法究竟是什么可以总结为三条：

1. 数据结构是数据对象在计算机中的组织方式
   • 逻辑结构
   • 物理存储结构
2. 数据对象必定与一系列加在其上的操作相关联
3. 完成这些操作所用的方法就是算法

抽象数据类型（Abstract Data Type, ADT）

组成：

• 数据类型
  • 数据对象集
  • 数据集合相关联的操作集

抽象数据类型隐藏了具体的实现：

• 与存放数据的机器无关
• 与数据存储的物理结构无关
• 与实现操作的算法和编程语言均无关

只描述了数据对象集合相关操作集“是什么”，并不涉及“如何做到”的问题。

抽象的好处：能简化对数据类型的描述，只需关心其如何存储数据，无需关心具体的不同的各种实现。

什么是算法

算法的定义

算法（Algorithm）

• 一个有限指令集
• 接受一些输入（不必须）
• 产生输出（必须，否则算法无意义）
• 一定在有限步骤之后终止
• 每条指令必须
  • 有充分明确目标，不可以有歧义
  • 计算机能处理的范围之内
  • 描述不依赖于任何一种计算机语言以及具体的实现手段——抽象

什么是好的算法

两个指标：

1. 空间复杂度 \(S(n)\) ——根据算法写成的程序执行时占用存储单元的长度
2. 时间复杂度 \(T(n)\) ——根据算法写成的程序在执行时耗费时间的长度

二者往往都与输入数据的规模有关。

参考之前的例子。函数 printN 的两种实现，使用递归的 \(S(n)=C n\)，而使用循环的是 \(S(n)=C\)；计算多项式则分析过，二的时间复杂度为 \(T(n)=C_1 n\)，而一的时间复杂度为 \(T(n)=C_1 n^2 + C_2 n\)。

在衡量时间复杂度的时候，可以近似为计算语句的执行次数，如 \(T(n)=C_1 n^2 + C_2 n\)。而在数据量很大的时候，一次项可以忽略不计，而常数项的影响不大。我们常取去除常数的最大项如 \(T(n)=O(n^2)\) 来描述时间复杂度。

两种常用时间复杂度

• 最坏情况复杂度 \(T_{worst}(n)\)
• 平均复杂度 \(T_{avg}(n)\)

\[ T_{avg}(n)\leqslant T_{worst}(n) \]

但是常分析最坏情况复杂度。因为问题不同，平均复杂度中的“平均”可能很难确定，因此会分析更容易的最坏复杂度。

复杂度的渐进表示法

我们在比较算法的效率的时候，不需要对算法进行精确分析，只需要粗略的知道它的一个增长趋势。因而有了复杂度的渐进表示法。

• \(T(n) = O(f(n))\) 表示存在常数 \(C > 0\) , \(n_0 > 0\) 使得当 \(n \geq n_0\) 时有 \(T(n) \leq C \cdot f(n)\)
• \(T(n) = \Omega(g(n))\) 表示存在常数 \(C > 0\) , \(n_0 > 0\) 使得当 \(n \geq n_0\) 时有 \(T(n) \geq C \cdot g(n)\)
• \(T(n) = \Theta(h(n))\) 表示同时有 \(T(n) = O(h(n))\) 和 \(T(n) = \Omega(h(n))\) 成立

一般有：

\(O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<\cdots <O(2^n)<O(n!)\)

复杂度分析小窍门

• 若两段算法分别有复杂度 \(T_1(n) = O(f_1(n))\) 和 \(T_2(n) = O(f_2(n))\) ，则
  • \(T_1(n) + T_2(n) = \max(O(f_1(n)), O(f_2(n)))\)
  • \(T_1(n) \times T_2(n) = O(f_1(n) \times f_2(n))\)
• 若 \(T(n)\) 是关于 \(n\) 的 \(k\) 阶多项式，那么 \(T(n) = \Theta(n^k)\) ，即只需考虑最大项
• 一个 for 循环的时间复杂度等于循环次数乘以循环体代码的复杂度
• if-else 结构的复杂度取决于 if 的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大者

应用实例

给定 \(N\) 个整数的序列 \(\{A_1, A_2, \ldots, A_N\}\) ，求函数 \(f(i, j) = \max\left\{0, \displaystyle\sum_{k=i}^{j} A_k\right\}\) 的最大值。

基础的三层循环可以求解这个问题，不过时间复杂度高达 \(O(n^3)\)

稍加优化，可以优化到 \(O(n^2)\)

下面分析分而治之的算法的时间复杂度。

分而治之与递归时间复杂度求解

将整个序列的最大子序列分为求左右两个子序列的最大子序列以及跨越中间线的最大子序列，三者的最大值即为结果。而左右子序列的最大子序列的求解方法也相同。可以使用递归算法来求解。

下面分析时间复杂度：

问题的时间复杂度写作 \(T(N)\)，那么子序列的时间复杂度就是 \(T(\dfrac{N}{2})\)。跨越中间线的最大子序列的求解时间复杂度为 \(O(n)\)。

于是有：

\[ \begin{array}{lll} T(N) &= 2T(\dfrac{N}{2})+cN, & T(1)=O(1) \\ &=2\left[2T(\dfrac{N}{2^2})+c\dfrac{N}{2}\right]+cN \\ &=2^k O(1) + ckN, & 其中\dfrac{N}{2^k}=1 \\ &=nO(1)+cN\log N\\ &=O(N\log N) \end{array} \]

求解递归类问题的时间复杂度，方法就是根据递归的逻辑，写出递推表达式，之后将其展开（有点像知道数列递推公式然后求数列通项公式）。

代码如下：

int Max3(int A, int B, int C)
{ /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}
int DivideAndConquer(int List[], int left, int right)
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum;             /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
    int LeftBorderSum, RightBorderSum;
    int center, i;
    if (left == right)
    { /* 递归的终止条件，子列只有1个数字 */
        if (List[left] > 0)
            return List[left];
        else
            return 0;
    } /* 下面是"分"的过程 */
    center = (left + right) / 2; /* 找到中分点 */ /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer(List, left, center);
    MaxRightSum = DivideAndConquer(List, center + 1, right); /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for (i = center; i >= left; i--)
    { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if (LeftBorderSum > MaxLeftBorderSum)
            MaxLeftBorderSum = LeftBorderSum;
    }
    /* 左边扫描结束*/ MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for (i = center + 1; i <= right; i++)
    { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if (RightBorderSum > MaxRightBorderSum)
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */ /* 下面返回"治"的结果 */
    return Max3(MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum);
}
int MaxSubseqSum3(int List[], int N)
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer(List, 0, N - 1);
}

在线处理算法

int MaxSubseqSum4(int A[], int N)
{
    int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for (i = 0; i < N; i++) {
        ThisSum += A[i]; /* 向右累加 */
        if (ThisSum > MaxSum)
            MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
        else if (ThisSum < 0) /* 如果当前子列和为负 */
            ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */
    }
    return MaxSum;
}

这个算法 \(T(N)=O(N)\)。

“在线”的含义：每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

关键收获

1. 递归类型算法的时间复杂度的计算方法
2. 在线处理算法（Kadane 算法）