# 算法简介 & 复杂度分析

# 什么是算法

我们会通过编程解决很多问题。当遇到问题时，首先要做的就是构造一个模型把问题转换为数学问题。

建立完模型后，我们需要定义一个具体过程，在放入输入后，它能够遵循一系列步骤得到输出。这一个具体过程就称为算法。

『 算法 』是用于解决某种计算问题的一个具体过程，其中包含的步骤数量是有限的。且同样的输入会得出同样的输出。

# 函数的增长

 算法执行所需的资源可以分为两类：

• 空间：内存，网络带宽，等...
• 时间

一般来说，算法执行需要的资源与输入的规模同步增长，所以通常把一个算法运行所需的资源，描述成关于其输入规模的 "函数"。

分析算法就是分析算法执行所需的资源 ( 时间，空间 )。

通常我们更关注的是所需的 “运行时间”。

因为算法运行的实际时间受 “计算机硬件配置” 和 “输入规模” 的影响很大。我们不可能每次都去实际测量真实所需时间。所以需要一种不用具体输入，就能估算算法执行效率的方法。

假定算法执行的每一步操作所需时间相同。一个算法在特定输入上的运行时间为：

通过估计 “当输入增长时一个算法所需操作数量的增长”。就能够判定当输入规模增大时用一个特定算法来求解该问题是否实际可行。并且可以比较多个算法以判断当输入规模增大时哪个算法更有效。

# 大 O 表示法

『 大 O 表示法 』 用来估计当输入增长时一个算法所需时间的增长。下面给出它的数学定义：

通过上面的定义和例子，可以看出：大 O 表示法，表示出了 $g(x)$ 的『 增长率 』大于等于 $f(x)$。也就是 $f(x)$ 是在以一个不快于 $g(x)$ 的速度增长。$g(x)$ 也被称为 $f(x)$ 的一个『 上界 』。

请记住，大 O 表示法只指示出$g(x)$ 的增长率比 $f(x)$ 大而已，并不表示它们的增长率很贴近，只是我们默认选取增长率最贴近的那个函数而已。

• 🌰 举例，如果 $g(x) = 2x^2$ 那么 $g(x) = O(x^4)$，$g(x) = O(x^3)$，$g(x) = O(x^2)$。在分析算法时，我们肯定会选取增长率和 $g(x)$ 最接近的那个上界，也就是 $x^2$。

# 大 Ω 表示法

可以看出来 “大 Ω 表示法” 就是把 “大 O 表示法” 倒过来说。

$g(x) = O(f(x))$ 当且仅当 $f(x) = Ω(g(x))$

大 Ω 表示法，表示出了 $g(x)$ 的『 增长率 』小于等于 $f(x)$。也就是 $f(x)$ 是在以一个不慢于 $g(x)$ 的速度增长。$g(x)$ 也被称为 $f(x)$ 的一个『 下界 』。

# 大 Θ 表示法

 简单说：$f(x) = Θ(g(x))$ 当且仅当 $f(x) = O(g(x))$ 并且 $f(x) = Ω(g(x))$

也就是说，$f(x)$ 的增长率既不会比 $g(x)$ 快，也不会比 $g(x)$ 慢，而是以相同的速率增长。

# 时间复杂度分析

在算法分析中，可以这样表示这个公式：

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

• $T(n)$ 表示代码执行的时间；
• $n$ 表示输入规模的大小；
• $f(n)$ 表示需要执行的操作次数的总和；

上面公式表示出：随着输入规模的增长，算法执行所需时间 $T(n)$ 的增长率小于需执行的操作次数 $f(n)$ 的增长率。

# 一些重要的定理

# 多项式定理

 如果 $T(n)$ 是个 $k$ 次多项式（最高次方为 $k$ 次）。那么 $T(n) = O(n^k)$。

 先看它的数学证明：

应用到算法分析中：

我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环执行次数最多的那一段代码就可以了。

int cal(int n) {
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

# 加法定理

在算法分析中：

一个算法的时间复杂度等于量级最大的那段代码的复杂度。

int cal(int n) {
  int sum_1 = 0;
  for (int p = 1;; p <= 100; ++p) {
    sum_1 = sum_1 + p;
  }

  int sum_2 = 0;
  for (int q = 1; q <= n; ++q) {
    sum_2 = sum_2 + q;
  }

  int sum_3 = 0;
  int i, j
  for (i = 1; i <= n; ++i) {
    for (j = 1;; j <= n; ++j) {
      sum_3 = sum_3 +  i * j;
    }
  }

  return sum_1 + sum_2 + sum_3;
}

# 乘法定理

一个算法中，嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

int cal(int n) {
  int ret = 0;
  for (int i = 1; i <= n; ++i) {
    ret = ret + f(i);
  }
}

int f(int n) {
  int sum = 0;
  for (int i = 1; i <= n; ++i) {
    sum = sum + i;
  }
  return sum;
}

# 常见的复杂度量级

下面介绍算法中常见的复杂度量级：

常数级别 $O(1)$

🌰 例如：两个数相加

a = b + c

对数级别 $O(logN)$

🌰 例如：二分查找算法

线性级别 $O(N)$

🌰 例如： 一个 for 循环

for(int i = 0; i < N; i++) {
  ...
}

线性对数级别 $O(NlogN)$

🌰 例如：归并排序

平方级别 $O(N^2)$

🌰 例如：两个 for 循环嵌套

for(int i = 0; i < N; i++) {
  for(int j = 0; j < N; j++) {
    ...
  }
}

🌰 立方级别 $O(N^3)$

例如：三个 for 循环嵌套

for(int i = 0; i < N; i++) {
  for(int j = 0; j < N; j++) {
    for(int k = 0; k < N; k++) {
      ...
    }
  }
}

指数级别 $O(2^N)$

阶乘级别 $O(N!)$

下图显示了随着输入规模的增长， 各个复杂度所运行花费时间时间的增长：

在实际开发中，我们总是希望可以找到 "线性对数级别"，"线性级别"，或者 "对数级别" 的复杂度的算法实现。

# 最好/最坏情况时间复杂度

『 最好情况时间复杂度 』，指该算法求解问题时，最少需要的运算次数。

『 最坏情况时间复杂度 』，指该算法求解问题时，最多需要的运算次数。

function findNum(arr, num) {
  var index = undefined;
  for (i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      index = i;
      break;
    }
  }
  return index;
}

# 平均情况时间复杂度

 最好/最坏时间复杂度都表现的是算法的极端情况表现。为了更好的表示算法日常的时间复杂度，我们采用『 平均情况时间复杂度 』

在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。只有同一个算法在不同的情况下，最好/最坏时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。

# 均摊时间复杂度

# 空间复杂度分析

时间复杂度表示的输入规模，和算法执行时间之间的增长关系。

空间复杂度表示的是输入规模，和储存空间之间的增长关系。

 可以看下面这段例子：

void xxx(n) {
  int[] arr = new int[n];
  for(int i = 0; i < n; i++) {
    arr[i] = i * 2;
  }
}

上面代码中 ，我们申请了一个长度为 n 的 int 类型数组。所以这段代码的空间复杂度为 $O(n)$。

在分析空间复杂度时，常见的复杂度级别也就是：$O(1)$、$O(n)$、$O(n^2)$。其他的很少见到。

# 常见数据结构的复杂度情况

# 算法面试问题解题步骤

我推荐大家用这个『 五步走 』模版来解决一个面试问题：

1. 明确题意。对于题目本身的描述，一些边界条件或者非法输入，提出自己的问题。像面试官表明你对问题已经有了一定的思考。
2. 描述一个大体思路。通常我们可以先给出一个最基本的暴力解法，再进一步去思考优化方法。
3. 写代码。
4. 测试。通过自己给的测试用例发现代码的潜在问题。
   • 通常我们给出一个边界用例，再结合一个常规用例。
   • 一步一步地通过语言描述你的算法做了什么，并且可以在标注当前的程序运行状态，来检验最后的答案是否正确；
5. 简单分析时间复杂度 & 空间复杂度。