确定给定代码的复杂度

确定给定代码的复杂度 通常 ，无法确定给定功能的复杂性

警告！文字墙传入！

1.有一种非常简单的算法，没人知道它们是否停止。

有没有算法，可以决定是否给定的程序暂停，或者没有，如果有一定的投入。计算复杂度是一个更加困难的问题，因为我们不仅需要证明算法停止运行，而且还需要证明算法停止运行的
速度 。

//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. 一些算法具有怪异和另类的复杂性

由于这些人，一般的“复杂性确定方案”很容易变得太复杂

//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.

有些功能非常简单，但会混淆许多静态分析尝试

//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));    }}

---

也就是说，我们仍然需要一种方法来查找事物的复杂性，对吗？For循环是一种简单且常见的模式。以您最初的示例为例：

for(i=0; i<N; i++){   for(j=0; j<i; j++){       print something   }}

由于每个

printsomething

都是O（1），因此算法的时间复杂度将取决于我们运行该行的次数。好吧，正如您的助教所提到的，我们通过查看这种情况下的组合来做到这一点。内部循环将运行（N
+（N-1）+ … + 1）次，总共（N + 1）* N / 2。

由于我们不考虑常数，所以得到O（N 2）。

现在，对于更棘手的情况，我们可以获得更多的数学信息。尝试创建一个函数，该函数的值表示在给定输入大小N的情况下算法运行所需的时间。
通常，我们通常可以直接从算法本身构造此函数的递归版本，因此计算复杂度成为对该函数设置界限的问题。 我们称此函数为 重复

例如：

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）只是古老的斐波那契函数。我们可以使用归纳法对此加以限制。

例如， 让我们通过归纳证明，对于所有N，T（N） <= 2 ^ n（即，T（N）为O（2 ^ n））

• 基本情况：n = 0或n = 1

  T(0) = 1 <= 1 = 2^0T(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

（我们也可以尝试做类似的事情来证明下界）

在大多数情况下，对函数的最终运行时间进行很好的猜测将使您能够轻松地用归纳证明解决重现性问题。 当然，这要求您首先能够猜测-
只有很多练习可以为您提供帮助。

最后一点，我想指出关于 Master定理
，这是我现在能想到的更常见的重复出现问题的唯一规则。当您必须处理棘手的分而治之算法时，请使用它。

---

另外，在您的“如果发生”示例中，我将通过将其作弊并将其分成两个独立的循环来解决此问题；里面有一个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++) { ... }    }}

具有与相同的运行时

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）。

请注意，我使用了一个很好的技巧来摆脱这里的“ if”。 没有通用的规则，如Collat​​z算法示例所示