数据结构基础（2）算法及算法分析
#数据结构#时间复杂度 2021-03-08

本文主要讲述了算法的基本概念和算法的分析方法，主要包括算法的时间复杂度分析.

目录（更新中）

参考资料

[1] 王红梅编著. 数据结构（C++版本）（第2版）. 北京：清华大学出版社，2011.

[2] 张铭. coursera-数据结构基础. coursera.

算法（Algorithm）

概述

算法被公认为是计算机科学的基石.

通俗地讲，算法是解决问题的方法. 现实生活中算法的实例不胜枚举，如一道菜谱、一个安装转移的操作指南等.

严格地说，算法是对特定问题求解步骤的一种描述，是指令的有限序列.

通常一个问题可以有多种算法，一个算法可以解决某个特定的问题.

算法必须满足以下 5 个重要特性：

  1. 输入：一个算法有零个或多个输入，这些输入通常取自于某个特定的对象集合.

  2. 输出：一个有一个或多个输出，通常输出与输入之间有着某种特定的关系.

  3. 有穷性：一个算法必须总是（对任何合法的输入）在执行有穷步之后结束，且每一步都在有穷时间内完成.

  4. 确定性：算法中每一条指令必须有确切的含义，不存在二义性。并且，在任何条件下，对于相同的输入只能得到相同的输出.

  5. 可行性：算法描述的操作过程可以通过已经实现的基本操作执行有限次来实现.

算法和程序不同. 原则上，算法可以用任何一种程序设计语言实现.

算法的有穷性意味着并不是所有的计算机程序都是算法，例如操作系统是一个在无限循环中执行的程序而不是一个算法. 然而我们可以把操作系统的各个任务看成是一个单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，得到输出结果后便终止.

优良性

一个“好"算法首先要满足算法的五大特性，此外还要具备下列特性.

  1. 正确性：对于任何合法的输入，算法都会得出正确的结果.

  2. 鲁棒性：也称健壮性，算法对非法输入的抵抗能力，即对于错误的输入，算法应能是被并做处理，而不是产生错误动作或陷入瘫痪.

  3. 简单性：算法容易理解和实现.

  4. 抽象分级：为了时算法便于阅读、理解、使用和修改，应使用抽象分级来组织算法表达的思想. 换言之，算法中的每一条逻辑步骤可以是一条简单的指令，也可以是一个模块，通过模块调用完成相应功能. 每个模块表示一种抽象，模块的内部描述了怎样实现抽象，而模块的名称描述了模块的功能.

  5. 高效性：算法的效率包括时间效率和空间效率.

描述方法

常用的描述算法的方法有：

  • 自然语言：容易理解；但准确性不佳，容易出现二义性.

  • 流程图：直观易懂；但严密性和灵活性欠佳，在描述复杂算法时极不方便.

  • 程序设计语言：能直接由计算机执行；但抽象性差，往往拘泥于描述算法的具体细节，容易失去算法的整体观，还要求算法设计者熟练掌握程序设计语言及其编程技巧.

  • 伪代码：表达能力上类似于编程语言，同时极小化了描述算法所不必要的技术细节，比较适合描述算法，被称为“算法语言”或“第一语言”.

伪代码（pseudo-code）是介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计. 至于算法中自然语言的成分有多少，取决于算法的抽象级别：往往抽象级别越高自然语言使用得越多.

算法分析

时间复杂度

显然，事后统计的方法可以准确的计算一个算法的效率. 但该方法至少有以下缺点：

  1. 编写程序实现算法将花费较多时间和精力，若事后统计发现算法效率并不理想，则编写程序的成分白白浪费.

  2. 所的实验结果依赖于计算机的软硬件等客观环境，有时容易掩盖算法本身的优劣.

因此，我们通常采用事前分析估算的方法——渐进复杂度（symptotic complexity）.

算法的时间复杂度

撇开与计算机软硬件有关的因素，影响算法时间代价的最主要因素是问题规模. 问题规模（problem scope）是指输入量的多少，一般来说，它可以从问题描述中得到.

显然，算法运行的时间 是问题规模 的函数，记作 T(n).

要精确表示算法的运行时间函数是很困难的，且即使能够给出往往也是个相当复杂的函数，这与我们摒弃“事后统计”的方法，希望通过“估算”来节约成本的原则违背. 在准确度与效率之间，“渐进时间复杂度”取得了一个良好的平衡.

渐进时间复杂度通过衡量算法中基本语句（basic statement）执行的次数，并且只关心其中随着问题规模增大对时间成本贡献最大的部分. 类似于高数中对于一个由多项式给出的无穷大，很多情况下，我们只需关注其中最高阶无穷大项即可.

高数中，对于极限 ，我们知道随着 的增大，第二项 对于整个多项式增大的贡献逐渐小于 ，直至可以忽略.

由以上讨论，我们给出渐近时间复杂度分析的常用方法：

  1. 大 表示法：若存在常数 ，对于任意 时，都有 ，则称 ，或称 在 中.

  2. 大 表示法：若存在常数 ，对于任意 时，都有 ，则称 ，或称 在 中.

  3. 大 表示法：若 既在 中，又在 中，则称 在 中. 更具体地，若存在常数 ，对于任意 时，都有 ，则称 ，或称 在 中.

不难理解：

  • 大 表示法给出算法时间复杂度的渐近上限，大 表示法给出渐近下限.
  • 大 和大 表示法往往是不唯一的. 为了尽可能精确，往往选择上（下）限中最“紧”的那个.
  • 当 时，有 .

其中大 表示法最为常用，且往往选择最“紧”的那个上限，即选择所有上限中最小的.

对于大 表示法，容易得到如下规则：

  1. 加法规则

  2. 乘法规则

最好、最坏和平均情况

对于某些算法，即使问题规模相同，如果输入数据不同，其时间开销也不同.

例如，在一维整型数组 中顺序查找与给定值 相等的元素：

1
2
3
4
5
6
7
8
9
10
/**
 * @param int[] 待查数组
 * @param int 数组长度
 * @returns 元素 k 的下标，返回 n 时表示查找失败
 */
int Find(int A[], int n) {
  for (i = 0; i < n; i++)
    if (A[i] == k) break;
  return i;
}

对于输入的数组 ，如果第一个元素恰好等于 ，算法只需要比较一次，这是最好的情况；如果直到最后一个元素才等于 ，则算法需要比较 次，这是最坏情况.

显然直接使用最好情况来估计算法性能是不合理的，因为它发生的概率往往是很小的，得到的结果将过于乐观了；当然最坏情况发生的概率往往也很小，但估计最坏情况下的算法性能是有意义的，即据此来保证某些系统的可靠性.

算法往往是对不同数据进行多此执行的，因此考虑平均情况是有必要的. 从概率统计的角度来讲，我们需要知道输入数据的分布情况，以此估计算法性能的“均值”.

比如，上例中，当我们知道 极大概率出现在第一个元素位置时，使用最好情况估算性能是合理的. 当我们对数据的分布一无所知时，采用“等同无知”原则，认为各数据元素是等概率分布的，则上例中平均要比较 个元素.

空间复杂度（space complexity）

算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量，即除算法本身和输入输出数据所占据的空间外，算法临时开辟的存储空间，通常记作：

其中， 为问题规模，分析方法与算法的时间复杂度类似.