确定给定代码的复杂性
给定一段代码，你将如何确定一般的复杂性。 我发现自己对Big O的问题感到困惑。 例如，一个非常简单的问题：
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println("*"); } } 电讯局长以类似组合的方式解释了这一点 就像这样，select2 =（n（n-1））/ 2 = n ^ 2 + 0.5，然后去掉这个常数使得它变成n ^ 2。 我可以把inttesting值，并尝试但这个组合的事情是怎么进来的？
如果这是一个if语句呢？ 复杂性如何确定？
for (int i = 0; i < n; i++) { if (i % 2 ==0) { for (int j = i; j < n; j++) { ... } } else { for (int j = 0; j < i; j++) { ... } } }
那么recursion呢？
int fib(int a, int b, int n) { if (n == 3) { return a + b; } else { return fib(b, a+b, n-1); } }
一般来说 ，没有办法确定给定函数的复杂性
警告！ 来文墙！
1.有非常简单的algorithm，没有人知道他们是否停止。
没有一个algorithm可以决定给定的程序是否停止，如果给定的input。 计算计算复杂度是一个更难的问题，因为我们不仅需要certificatealgorithm暂停，而且还需要certificatealgorithm有多快 。
//The Collatz conjecture states that the sequence generated by the following // algorithm always reaches 1, for any initial positive integer. It has been // an open problem for 70+ years now. function col(n){ if (n == 1){ return 0; }else if (n % 2 == 0){ //even return 1 + col(n/2); }else{ //odd return 1 + col(3*n + 1); } }
2. 一些algorithm具有怪异和不合拍的复杂性
一般的“复杂性决定scheme”很容易因为这些人而变得复杂
//The Ackermann function. One of the first examples of a non-primitive-recursive algorithm. function ack(m, n){ if(m == 0){ return n + 1; }else if( n == 0 ){ return ack(m-1, 1); }else{ return ack(m-1, ack(m, n-1)); } } function f(n){ return ack(n, n); } //f(1) = 3 //f(2) = 7 //f(3) = 61 //f(4) takes longer then your wildest dreams to terminate.
3. 一些function非常简单，但会混淆许多种静态分析尝试
//Mc'Carthy's 91 function. Try guessing what it does without // running it or reading the Wikipedia page ;) function f91(n){ if(n > 100){ return n - 10; }else{ return f91(f91(n + 11)); } }
这就是说，我们仍然需要一种方法来find东西的复杂性，对吧？ For循环是一个简单和常见的模式。 拿你最初的例子：
for(i=0; i<N; i++){ for(j=0; j<i; j++){ print something } }
由于每个print something是O（1），algorithm的时间复杂度将取决于我们运行该行的次数。 那么，正如你的技术援助提到的那样，我们通过查看这种情况下的组合来做到这一点。 内循环将运行（N +（N-1）+ … + 1）次，总共为（N + 1）* N / 2。
由于我们忽略常量，所以得到O（N 2 ）。
现在更棘手的情况下，我们可以得到更多的math。 尝试创build一个函数，其值代表algorithm运行多长时间，给定input的大小N. 通常我们可以直接从algorithm本身构造这个函数的recursion版本，因此计算复杂度就成了这个函数的界限。 我们称这个函数为一个重复
例如：
function fib_like(n){ if(n <= 1){ return 17; }else{ return 42 + fib_like(n-1) + fib_like(n-2); } }
很容易看出以N来表示的运行时间将由下式给出
T(N) = 1 if (N <= 1) T(N) = T(N-1) + T(N-2) otherwise
那么，T（N）就是古老的斐波纳契函数。 我们可以使用归纳来解决这个问题。
例如， 让我们通过归纳certificate对于所有N（即T（N）是O（2 ^ n））T（N）<= 2 ^ n）
- 基本情况：n = 0或n = 1
T(0) = 1 <= 1 = 2^0 T(1) = 1 <= 2 = 2^1
- 归纳情况（n> 1）：
T(N) = T(n-1) + T(n-2) aplying the inductive hypothesis in T(n-1) and T(n-2)... T(N) <= 2^(n-1) + 2^(n-2) so.. T(N) <= 2^(n-1) + 2^(n-1) <= 2^n
（我们可以尝试类似的方法来certificate下界）
在大多数情况下，对函数的最终运行时间有一个很好的猜测，可以让您轻松地用归纳certificate来解决循环问题。 当然，这需要你能够猜到第一 – 只有很多的练习可以帮助你在这里。
作为最后一点，我想指出关于主定理的问题，这是现在常见的更复杂的问题的唯一规则。 当你必须处理一个棘手的分而治之algorithm时使用它。
另外，在你的“if case”例子中，我会通过作弊和分裂成两个单独的循环来解决这个问题。 有一个如果里面。
for (int i = 0; i < n; i++) { if (i % 2 ==0) { for (int j = i; j < n; j++) { ... } } else { for (int j = 0; j < i; j++) { ... } } }
与。运行时相同
for (int i = 0; i < n; i += 2) { for (int j = i; j < n; j++) { ... } } for (int i = 1; i < n; i+=2) { for (int j = 0; j < i; j++) { ... } }
而且这两个部分中的每一个都可以很容易地看作是O（N ^ 2），总数也是O（N ^ 2）。
请注意，我使用了一个很好的技巧来摆脱这里的“如果”。 这样做没有一般的规则，如Collatzalgorithm示例所示
一般来说，决定algorithm的复杂度在理论上是不可能的。
然而，一个很酷的，以代码为中心的方法实际上是直接从程序angular度思考。 举个例子：
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println("*"); } }
现在我们要分析它的复杂性，所以让我们添加一个简单的计数器来计算内线的执行次数：
int counter = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.println("*"); counter++; } }
因为System.out.println行并不重要，所以让我们删除它：
int counter = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { counter++; } }
现在我们只剩下了柜台，我们显然可以简化内部循环：
int counter = 0; for (int i = 0; i < n; i++) { counter += n; }
…因为我们知道增量正好运行n次。 现在我们看到计数器正好n次增加n ，所以我们简化为：
int counter = 0; counter += n * n;
我们出现了（正确的）O（n 2 ）复杂性:)它在代码中:)
让我们看看这是如何工作的recursion斐波那契计算器：
int fib(int n) { if (n < 2) return 1; return fib(n - 1) + fib(n - 2); }
改变例程，使其返回里面的迭代次数，而不是实际的斐波那契数字：
int fib_count(int n) { if (n < 2) return 1; return fib_count(n - 1) + fib_count(n - 2); }
这仍然是斐波那契！ :)所以我们现在知道recursion斐波那契计算器的复杂度是O（F（n）），其中F是斐波那契数。
好的，让我们看看更有趣的事情，说简单（和低效率）mergesort：
void mergesort(Array a, int from, int to) { if (from >= to - 1) return; int m = (from + to) / 2; /* Recursively sort halves */ mergesort(a, from, m); mergesort(m, m, to); /* Then merge */ Array b = new Array(to - from); int i = from; int j = m; int ptr = 0; while (i < m || j < to) { if (i == m || a[j] < a[i]) { b[ptr] = a[j++]; } else { b[ptr] = a[i++]; } ptr++; } for (i = from; i < to; i++) a[i] = b[i - from]; }
因为我们对实际结果不感兴趣，而且对复杂性不感兴趣，所以我们改变例程，以便实际返回所执行的工作单元的数量：
int mergesort(Array a, int from, int to) { if (from >= to - 1) return 1; int m = (from + to) / 2; /* Recursively sort halves */ int count = 0; count += mergesort(a, from, m); count += mergesort(m, m, to); /* Then merge */ Array b = new Array(to - from); int i = from; int j = m; int ptr = 0; while (i < m || j < to) { if (i == m || a[j] < a[i]) { b[ptr] = a[j++]; } else { b[ptr] = a[i++]; } ptr++; count++; } for (i = from; i < to; i++) { count++; a[i] = b[i - from]; } return count; }
然后，我们删除那些实际上并不影响计数的行，并简化：
int mergesort(Array a, int from, int to) { if (from >= to - 1) return 1; int m = (from + to) / 2; /* Recursively sort halves */ int count = 0; count += mergesort(a, from, m); count += mergesort(m, m, to); /* Then merge */ count += to - from; /* Copy the array */ count += to - from; return count; }
还简化了一下：
int mergesort(Array a, int from, int to) { if (from >= to - 1) return 1; int m = (from + to) / 2; int count = 0; count += mergesort(a, from, m); count += mergesort(m, m, to); count += (to - from) * 2; return count; }
现在我们可以放弃这个数组了：
int mergesort(int from, int to) { if (from >= to - 1) return 1; int m = (from + to) / 2; int count = 0; count += mergesort(from, m); count += mergesort(m, to); count += (to - from) * 2; return count; }
现在我们可以看到，实际上从零开始的绝对值并不重要，而只是它们的距离，所以我们将其修改为：
int mergesort(int d) { if (d <= 1) return 1; int count = 0; count += mergesort(d / 2); count += mergesort(d / 2); count += d * 2; return count; }
然后我们得到：
int mergesort(int d) { if (d <= 1) return 1; return 2 * mergesort(d / 2) + d * 2; }
这里显然在第一次调用d是要sorting的数组的大小，所以你有复杂的M（x）（这是在第二行:)
M(x) = 2(M(x/2) + x)
而这个你需要解决才能得到一个封闭的表单解决scheme。 这个你通过猜测解M（x）= x log x来做到最简单，并且validation右边：
2 (x/2 log x/2 + x) = x log x/2 + 2x = x (log x - log 2 + 2) = x (log x - C)
并validation它是渐近等价于左侧：
x log x - Cx ------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1. x log x
尽pipe这是一个过于泛化的问题，但是我喜欢用列表的方式来思考Big-O，列表的长度是N个项目。
因此，如果你有一个遍历列表中的所有东西的for循环，它是O（N）。 在你的代码中，你有一行（全部是孤立的）是0（N）。
for (int i = 0; i < n; i++) {
如果你有一个嵌套在for循环中的for循环，并且你需要查看列表中的每个项目，那么你对每个项目执行一个操作，那么你对N个项目中的每一个都进行N次操作，因此O（N ^ 2）。 在上面的例子中，事实上，在for循环中嵌套了另一个for循环。 所以你可以把它看作每个for循环是0（N），然后因为它们是嵌套的，把它们相乘得到一个总的值0（N ^ 2）。
相反，如果你只是在一个单一的项目快速操作，那么这将是O（1）。 没有“长度列表n”去遍历，只是一个单一的操作。把这个放在上下文中，在你上面的例子中，操作：
if (i % 2 ==0)
是0（1）。 重要的不是“如果”，而是检查单个项目是否与另一个项目相同的事实是对单个项目的快速操作。 像以前一样，if语句嵌套在你的外部for循环中。 然而，因为它是0（1），所以你把所有的东西都乘以1，所以在你最终计算整个函数的运行时间时没有“明显的”影响。
对于日志，处理更复杂的情况（比如这个计数到j或i的业务，而不是再次），我会指出你在这里更加优雅的解释。
我喜欢用Big-O符号来做两件事：标准的Big-O，这是最坏的情况，平均的Big-O，这是通常最终发生的事情。 它也帮助我记住Big-O符号试图将运行时间近似为input数量N的函数。
电讯局长以类似组合的方式解释了这一点 就像这样，select2 =（n（n-1））/ 2 = n ^ 2 + 0.5，然后去掉这个常数使得它变成n ^ 2。 我可以把inttesting值，并尝试但这个组合的事情是怎么进来的？
正如我所说，正常的大O是最坏的情况。 你可以试着去计算每一行被执行的次数，但是看看第一个例子并且说在n的长度上有两个循环，一个embedded到另一个循环中是比较简单的，所以它是n * ñ。 如果他们是一个接一个的，那就是n + n，等于2n。 由于其近似，你只是说n或线性。
如果这是一个if语句呢？ 复杂性如何确定？
这是我的平均情况和最好的情况下帮助我组织我的想法很多。 在最坏的情况下，你忽略了如果说n ^ 2。 在一般情况下，对于你的例子，你有一个循环n，另一个循环的一部分n发生了一半的时间。 这给你n * n / x / 2（x是在你的embedded循环中循环的n的任何一个分数，这给你n ^ 2 /（2x），所以你会得到n ^ 2一样的。是因为它是一个近似值。
我知道这并不是你的问题的完整答案，但是希望这对于接近代码中的复杂性有一些帮助。
正如我在上面的答案中所说，显然不可能为所有代码片断确定这一点; 我只是想增加使用一般情况下的大O的想法讨论。
对于第一个片段，这只是n ^ 2，因为您执行n次操作n次。 如果j初始化为i ，或者到了i ，那么你发布的解释会更合适，但是现在看来并不是这样。
对于第二个片段，你可以很容易地看到第一个执行的时间有一半，第二个执行半个时间。 根据里面的内容（希望它取决于n ），可以将方程改写为recursion方程。
recursion方程（包括第三个片段）可以这样写：第三个将显示为
T(n) = T(n-1) + 1
我们可以很容易看到的是O（n）。
Big-O只是一个近似值，并没有说algorithm需要多长时间才能执行，只是说了input大小增长需要多长时间。
所以如果input的大小是N，algorithm评估一个恒定复杂度的expression式：O（1）N次，algorithm的复杂度是线性的：O（N）。 如果expression式具有线性复杂度，则该algorithm具有二次复杂度：O（N * N）。
一些expression式具有指数复杂度：O（N ^ N）或对数复杂度：O（logN）。 对于循环和recursionalgorithm，乘以循环和/或recursion的每个级别的复杂性。 就复杂性而言，循环和recursion是等价的。 algorithm在algorithm的不同阶段具有不同的复杂度，select最高的复杂度而忽略其余部分。 （5）与O（1）相同，O（5 * N）与O（N）相同。
