算法概述

算法 Algorithm 广义上指解决问题的方法。

是指接替方案的准确且完整的描述

是一系列解决问题的清晰指令

是用系统的方法解决问题的策略机制

以一定规范的输入，在有限的时间内获得所要求的输出

如排序算法，暴力枚举算法，贪心算法，分治算法，二分搜索算法，深搜算法，广搜算法，动态规划算法等。

算法特征

1. 有穷性：有限步骤停止
2. 确切性：每一步骤有明确的定义
3. 输入项：0 个或多个输入
4. 输出项：一个或多个输出。没有输出的算法，或者说没有结果的算法是无意义的
5. 可行性：算法中执行的任何计算步骤都是可以被分解为基本执行步骤，也称之为有效性

算法复杂度

也称时空复杂度，从时间和空间两个维度来讨论一个算法的优劣性：

• 时间复杂度
• 空间复杂度

当前阶段，主要考量的是时间复杂度。但实际上这是一个非常复杂的内容，现阶段也只是做一些简单的理解即可。

执行一个语句，表示一个时间频度，时间复杂度主要是对时间频度 T 的描述和表达。

为了简化描述，利用大 O 记法对时间频度 T 进行化简。

大 O 记法

1. O(1) 代表所有常数时间复杂度
2. 在修改后的运行次数函数中 T(n)，只保留最高阶；
3. 如果最高阶存在且不是 1，则删去掉与这个项相乘的常数；

常数阶

int a = 100; // 1 语句
int sum = (1 + a) * a / 2; // 1 语句
cout << sum << endl; // 1 语句

时间频度 $T(n) = 3$

以大 O 记法优化则 $O(T(n)) = O(3) = O(1)$

线性阶

int sum = 0;                    // 1 次
for (int i = 1; i <= n; i ++) { // n 次
    sum += i;                   // n 次
}
cout << sum << endl;            // 1 次

时间频度 $T(n) = 2+2n$

以大 O 记法优化则 $O(T(n)) = O(2+2n) = O(n)$

平方阶

for (int i = 1; i <= n; i ++) {   // n 次
  for (int j = 1; j <= n; j ++) { // n*n 次
    // O(1) 语句
  }
}

时间频度 $T(n) = n + n^2$

以大 O 记法优化则 $O(T(n))=O(n+n^2) = O(n^2)$

对数阶

int i = 1;
while (i < n) {
  i *= 2; // 设为 T 次
}

时间频度 $T$ 有 $2^T<n$

两边取对数有 $T<log_2(n)$ 整理可以取极限 $T=log(n)$

以大 O 记法优化则 $O(T(n)) = O(log(n))$

简单练习

1. 以下代码的时间复杂度是

int s = 0;
for (int i = 2; i <= n / i; i ++) {
    if (n % i == 0) s += i;
}

{{ select(1) }}

• $O(n)$
• $O(\sqrt{n})$
• $O(n^2)$
• $O(log(n))$