Coding ManJava算法复杂度
1. 概述
在本教程中，我们将讨论Big O Notation 的含义。我们将通过几个示例来研究它对代码运行时间的影响。
2.大O符号的直觉
我们经常听到使用**Big O Notation 描述的算法的性能。**
算法性能的研究——或算法复杂性——属于算法分析 领域。算法分析回答了算法消耗了多少资源（例如磁盘空间或时间）的问题。
我们将时间视为一种资源。通常，算法完成所需的时间越少越好。
3. 恒定时间算法
算法的这种输入大小如何影响其运行时间？了解 Big O 的关键是了解事物的增长速度。这里所讨论的速率是每个输入大小所花费的时间。
考虑这段简单的代码：
int n = 1000;
System.out.println("Hey - your input is: " + n);
显然，上面的n是什么并不重要。这段代码需要一定的时间来运行。它不依赖于 n 的大小。 相似地：
int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);
上面的例子也是常数时间。即使运行时间是原来的 3 倍，它也不取决于输入的大小 n。我们将恒定时间算法表示如下：$$ O \left ( 1 \right ) $$。请注意，$$ O \left ( 1 \right ) $$、$$ O \left ( 1 \right ) $$甚至$$ O \left ( 1 \right ) $$都意味着同样的事情。
我们并不关心运行需要多长时间，只关心它需要恒定的时间。
4. 对数时间算法
恒定时间算法（渐近地）是最快的。**对数时间是第二快的。**不幸的是，它们有点难以想象。
对数时间算法$$ O \left ( \log_{}{n} \right ) $$ 的一个常见示例是二进制搜索 算法。要了解如何在 Java 中实现二进制搜索，请单击此处 。
这里重要的是运行时间与输入的对数成比例增长（在这种情况下，以 2 为底的对数）：
for (int i = 1; i < n; i = i * 2){
System.out.println("Hey - I'm busy looking at: " + i);
}
如果n为 8，则输出将如下所示：
Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4
我们的简单算法运行 log(8) = 3 次。
5. 线性时间算法
在对数时间算法之后，我们得到了下一个最快的类：线性时间算法。
如果我们说某些东西线性增长，我们的意思是它的增长与其输入的大小成正比。
想一个简单的 for 循环：
for (int i = 0; i < n; i++) {
System.out.println("Hey - I'm busy looking at: " + i);
}
这个 for 循环运行多少次？n次，当然！我们不确切知道这需要多长时间才能运行 - 我们并不担心这一点。
我们所知道的是，上面介绍的简单算法将随着其输入的大小线性增长。
我们更喜欢 0.1n 的运行时间而不是( 1000n + 1000 )，但两者仍然是线性算法；它们都与投入的规模成正比增长。
同样，如果算法更改为以下内容：
for (int i = 0; i < n; i++) {
System.out.println("Hey - I'm busy looking at: " + i);
System.out.println("Hmm.. Let's have another look at: " + i);
System.out.println("And another: " + i);
}
运行时的输入大小仍然是线性的，n。我们将线性算法表示如下：$$ O \left ( n \right ) $$。
与恒定时间算法一样，我们不关心运行时的细节。**$$ O \left ( 2n+1 \right ) $$与$$ O \left ( n \right ) $$**相同，因为 Big O Notation 关注输入大小的增长。
6. N Log N 时间算法
**$$ O \left ( n\log_{}{n} \right ) $$是下一类算法。**运行时间与输入的$$ n\log_{}{n} $$成比例增长：
for (int i = 1; i <= n; i++){
for(int j = 1; j < n; j = j * 2) {
System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
}
}
例如，如果 n为 8，则此算法将运行8 * log(8) = 8 * 3 = 24次。对于大 O 表示法，我们在 for 循环中是否有严格的不等式是无关紧要的。
7. 多项式时间算法
接下来我们有多项式时间算法。这些算法甚至比$$ n\log_{}{n} $$算法还要慢。
多项式是包含二次$$ n^{2} $$、三次$$ n^{3} $$、四次$$ n^{4} $$等函数的通用项。重要的是要知道$$ O \left ( n^{2} \right ) $$比$$ O \left ( n^{3} \right ) $$快，$$ O \left ( n^{3} \right ) $$比$$ O \left ( n^{4} \right ) $$快，等等。 让我们看一个二次时间算法的简单示例：
for (int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
}
}
该算法将运行 8 2 = 64次。请注意，如果我们要嵌套另一个 for 循环，这将成为$$ O \left ( n^{3} \right ) $$算法。
8. 指数时间算法
现在我们正在进入危险的领域；这些算法与输入大小取幂的某个因子成比例增长。
例如，**$$ O \left ( 2^{n} \right ) $$算法每增加一个输入就会翻倍。**因此，如果n = 2，这些算法将运行四次；如果n = 3，它们将运行八次（有点像对数时间算法的反面）。
$$ O \left ( 3^{n} \right ) $$算法每增加一个输入就增加三倍，$$ O \left ( k^{n} \right ) $$算法每增加一个输入就会增加 k 倍。
让我们看一个$$ O \left ( 2^{n} \right ) $$时间算法的简单示例：
for (int i = 1; i <= Math.pow(2, n); i++){
System.out.println("Hey - I'm busy looking at: " + i);
}
该算法将运行$$ 2^{8} = 256 $$次。
9. 阶乘时间算法
在大多数情况下，这几乎和它会得到的一样糟糕。这类算法的运行时间与 输入大小的阶乘 成正比。
一个典型的例子是 使用蛮力方法解决旅行商问题 。
旅行商问题的解决方案的解释超出了本文的范围。
相反，让我们看一个简单的$$ O \left ( n! \right ) $$算法，如前几节所示：
for (int i = 1; i <= factorial(n); i++){
System.out.println("Hey - I'm busy looking at: " + i);
}
其中 *factorial(n)*只计算 n!。如果 n 为 8，则此算法将运行$$ 8! = 40320 $$ 次。
10. 渐近函数
**大 O 就是所谓的渐近函数。**所有这一切意味着，它关注的是算法在极限下的性能——即——当大量输入被抛出时。
Big O 并不关心您的算法对小尺寸输入的效果如何。它与大输入有关（考虑对一百万个数字的列表进行排序与对 5 个数字的列表进行排序）。
另一件需要注意的是，**还有其他渐近函数。**Big Θ (theta) 和 Big Ω (omega) 也都描述了极限的算法（请记住， 这个极限仅仅意味着巨大的输入）。
要了解这三个重要函数之间的区别，我们首先需要知道 Big O、Big Θ 和 Big Ω 中的每一个都描述了一个集合（即元素的集合）。
在这里，我们集合的成员本身就是算法：
- Big O 描述了运行速度不低于某个速度的所有算法的集合（这是一个上限）
- 相反，Big Ω 描述了运行速度不超过特定速度的所有算法的集合 （这是一个下限）
- 最后，Big Θ 描述了以一定速度运行的所有算法的集合 （就像相等）
我们上面的定义在数学上并不准确，但它们会帮助我们理解。
通常，您会听到使用 Big O 描述的内容，但了解 Big Θ 和 Big Ω 并没有什么坏处。