算法复杂度

“算法是一种抽象的解决方案，描述了解决问题的过程，无论是通过人类、计算机还是其他手段。这是一种非常广泛的概念，具有无数的应用。”——大卫·哈雷尔，《算法学：计算精神》。

算法的本质与创造性
算法是问题的概念性解决方案。它们以计算机能够执行的基本工作单元描述，从而与具体的编程语言或执行环境无关。正如弗朗西斯·沙利文所说：“对我来说，优秀的算法是计算的诗歌。就像诗句，它们可以简洁、深奥、密集，甚至神秘。但一旦解锁，它们会以一种全新的光芒照亮计算的某些方面。”我们可以用伪代码和流程图等抽象符号记录算法。

当算法通过编程实现后，它们就被赋予了生命，成为程序的一部分。程序是计算机可执行的形式，是计算机区别于其他机器的特性之一。例如，微波炉只能加热食物，而不能洗衣服。但计算机却可以根据不同的程序执行不同的功能，其功能是可扩展的。若将计算机比作汽车，程序员是驾驶员，可以操控汽车完成各种任务；用户则是乘客，利用汽车提供的功能。这也说明学习编程的重要性：它让你可以自由控制计算机去完成各种任务。

算法的正确性
算法必须正确才能有用。在编写程序之前，必须仔细检查算法以消除错误。若算法本身有误，就无法编写出正确的程序。我们常提醒学生，若算法在纸面上无法正确运行，它也不会在计算机上正常工作。因此，先在纸上推演算法是至关重要的。

即使算法设计正确，也可能在编程过程中引入错误。编程错误分为两类：

  1. 语法错误
    • 编程语言有语法规则，违反规则会引入语法错误。这类错误容易修复，现代编程编辑器通常能检测并提示这些问题。
  2. 逻辑错误（软件 Bug）
    • 即使程序语法正确，其逻辑可能错误，导致程序的行为不符合预期。例如，程序像一份语法正确但指令含糊的菜谱。现代计算机的错误检测机制很完善，因此计算机很少犯错误。程序结果出错通常是人类的错误。

Bug 的起源
“Bug”一词最初源于硬件故障——一只飞蛾卡在了电机计算机中。现在，Bug 通常指计算机系统（硬件和软件）的任何错误或故障。例如：

  • 程序崩溃：程序无法继续执行。
  • 死循环：程序永远无法结束。

调试与测试
Bug 是不可避免的，因为人类会犯错。那么如何修复 Bug 以确保程序的正确性？答案是测试和调试：

  1. 测试

    • 一个测试由程序的样本输入和期望输出组成。运行测试时，将样本输入提供给程序，检查实际输出是否与期望输出一致。
    • 若匹配，则测试通过；否则，程序或测试存在 Bug。通常用一组测试（测试集）来覆盖算法的不同部分。

  2. 调试伪代码

    对于测试集中每个测试：
    运行程序并比较实际输出与期望输出
    如果匹配，继续下一个测试
    否则，修复 Bug 并重复整个过程

测试的局限性

  • 测试很难覆盖所有可能的情况，尤其是对于复杂程序。随着程序复杂度增加，需要的测试数量快速增长。
  • 正如艾兹赫尔·戴克斯特拉所说：“程序测试可以用于证明 Bug 的存在，但不能证明它们不存在！”

形式化验证
对于某些关键任务（如计算机处理器的微代码），可以通过形式化验证来证明程序的正确性。尽管测试不能保证程序无 Bug，但它是验证程序的重要步骤。

总结
算法是解决问题的核心工具，但必须确保其正确性和高效性。通过设计、测试和调试，我们可以将抽象的算法转化为可靠的程序。随着算法复杂度的增加，验证算法的正确性也变得更加重要。

算法的优劣性

为什么需要评价算法的优劣？
同一个问题往往有多种解决方案，也就会有多种算法可以让计算机解决该问题。在确保算法正确的前提下，我们还希望能够比较和评价这些算法。算法设计的“优劣性”评判标准可以包括以下几个方面：

  • 简洁性
  • 实现的难易程度
  • 执行速度
  • 结果的精确性

在计算领域，我们最关注的是算法的执行速度，因为快速的算法能够在相同的时间内解决更大的问题或更多的问题。这种关注效率的理念也体现在许多其他经济领域。例如，一个预测明天天气的程序如果需要运行 24 小时才能得出结果，那么几乎是没有用的。

如何衡量算法的“速度”？
一种方法是将算法实现为程序，运行程序并测量其执行时间（程序开始到结束的时间）。然而，这种方法存在以下挑战：

  1. 实现成本
    • 实现算法可能需要大量工作。
  2. 输入一致性
    • 为了比较两个程序的执行时间，必须提供相同的输入（如一个包含一百万个数字的排序列表），但输入大小可能无法理想地反映实际情况。
  3. 运行环境的影响
    • 程序的执行速度受硬件配置等因素影响。例如，同样的食谱，不同厨师的准备时间会有所不同，而所需的食材量也会进一步放大这种差异。

算法的内在特性
尽管运行环境会影响执行速度，算法本身的设计对速度的影响更为关键。例如：

  • 如果一份食谱要求每次打一个鸡蛋并分别搅拌，与一次性打破所有鸡蛋并搅拌相比，前者显然更慢，因为步骤更多。
  • 类似地，计算机算法中步骤的安排与组织方式对程序的运行时间有显著影响。

算法复杂度分析
由于算法是问题的抽象解决方案，我们希望在不实际实现的情况下研究其“速度”。这就是计算机科学中的算法分析。

  1. 步骤计数

    • 分析伪代码或流程图，计算工作单元（步骤）的数量。
    • 步骤数量通常是输入大小的函数。例如，若算法要求逐个打鸡蛋并搅拌，所需时间与鸡蛋数量成正比。

  2. 增长函数

    • 关注步骤数量与输入大小之间的关系，而非具体输入大小对应的步骤数量。
    • 增长函数揭示了工作量（成本）随输入规模增长的模式。

  3. 渐近分析

    • 使用渐近分析（asymptotic analysis）比较函数在输入趋于无穷时的表现：
      • 忽略不重要的细节（如不同操作单元耗时的微小差异）。
      • 关注任务中最复杂的部分，因为它将主导总成本。
    • 例如：
      • 一个快速步骤（耗时 0.0001 秒/次）重复 10 次，一个慢步骤（耗时 10 秒/次）不重复。
      • 若输入规模 NN 大于 10,000，快速步骤的总成本超过慢步骤。

  4. 分类和大 O 表示法

    • 简化后的增长函数被归入不同的复杂度类别。
    • 使用大 O 表示法表示每个类别，算法按类别进行排名。

关键概念总结

  • 算法与程序的区别
    • 算法是抽象的概念性解决方案，程序是具体的可执行代码。算法的性能定义是抽象的，无法直接测量。
  • 优劣评判的内在标准
    • 算法的优劣取决于其设计的“巧妙性”，而不是实现细节或运行环境。
  • 时间成本与输入大小的关系
    • 时间成本可用增长函数表示，随着输入大小增加，非主导项的影响可忽略。
  • 复杂度分类
    • 算法被归入不同复杂度类别，低复杂度算法在输入规模足够大时表现更优。

效率与复杂度的关系
效率与复杂度成反比：复杂度越高的算法，效率越低，因为它更复杂，导致计算资源的利用率降低。通过算法分析，我们可以在实现算法之前评估并比较它们的性能，为程序设计提供有力支持。

示例分析

在计算 1 到 NN 的所有数之和时，至少有以下两种算法：

  1. 算法 1：逐个手动累加
  2. 算法 2：使用公式计算： Sum=N×(N+1)2\text{Sum} = \frac{N \times (N + 1)}{2}

问题：如果手动执行这两个算法，哪一个更快？

  • 当 N=2N = 2？
  • 当 N=100N = 100？
  • 当 N=1,000,000N = 1,000,000？

算法实现与分析

算法 1 的实现
算法 1 使用循环将范围内的每个数字逐个相加，代码如下：

# Snap! 程序块，逐个累加两个数之间的所有数字并返回结果
repeat (N - 1) times:
    sum = sum + next_number

算法 2 的实现
算法 2 使用公式直接计算和，代码如下：

# Snap! 程序块，使用公式计算范围内所有数字的和并返回结果
report ((N * (N + 1)) / 2)

输入规模与算法性能

两种程序的输入均为范围的两个数（起点和终点）。我们将输入规模（问题规模）定义为范围内的数字个数 NN。

  • 算法 1： 随着 NN 的增加，执行时间稳步增长。
  • 算法 2： 无论 NN 增加多少，执行时间不变。

算法分析

  1. 算法 1：
    该算法的成本（执行步骤数量）与输入规模 NN 成正比：

    f=a+b⋅Nf = a + b \cdot N

    aa 是变量初始化的固定成本，bb 是每次加法的固定成本。随着 N→∞N \to \infty，我们可以忽略常数项，简化为：

    f=Nf = N

    这种增长属于线性时间复杂度，记为 O(N)O(N)。

  2. 算法 2：
    无论 NN 大小，该算法总是执行相同的操作，因此属于常数时间复杂度，记为 O(1)O(1)。

其他问题分析

问题：列表中的数字是否唯一？

算法：

  1. 比较列表中的第一个数字与所有其他数字。如果发现相同数字，则直接返回“否”。
  2. 将下一个数字与所有其他数字进行比较，重复步骤 1。
  3. 如果所有数字均不重复，则返回“是”。

**输入规模：**列表的长度 NN。

  • **最坏情况：**列表中的所有数字均唯一。此时，每个数字都需要与其他 N−1N - 1 个数字比较，总比较次数为： f=N⋅(N−1)f = N \cdot (N - 1) 简化后为： f=N2f = N^2 这类算法属于平方时间复杂度，记为 O(N2)O(N^2)。

问题：生成所有 n 位数字

算法：

  1. 从数字 0 到 9 中选择第一个数字。
  2. 对剩下的 n−1n-1 位数字递归生成所有可能组合。
  3. 将每个组合与首位数字拼接，形成 nn 位数字。

分析： 生成 nn 位数字需要输出 10n10^n 个数字。此类算法属于指数时间复杂度，记为 O(2N)O(2^N)。

总结与启示

  1. **线性时间复杂度 O(N)O(N)：**如累加算法，随输入规模线性增长。
  2. **平方时间复杂度 O(N2)O(N^2)：**如比较列表是否唯一，适合小规模输入。
  3. **指数时间复杂度 O(2N)O(2^N)：**如生成所有 n 位数字，成本随着输入规模快速增加。

实际应用： 算法复杂度直接影响程序性能。高效算法（如快速排序）通常能显著减少执行时间。以下视频展示了冒泡排序与快速排序的性能差异：

。

Last modified: Saturday, 11 January 2025, 5:13 PM