确定给定代码的复杂性

Question

给出一小段代码,您将如何确定一般的复杂性.我发现自己对Big O问题非常困惑.例如,一个非常简单的问题:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
    }
}

电讯局长用类似的东西解释了这一点.像这样是n选择2 =(n(n-1))/ 2 = n ^ 2 + 0.5,然后移除常数使其变为n ^ 2.我可以把int测试值和尝试但是这个组合的东西怎么样？

如果是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++) { ... }
    }
}

那么递归呢......

int fib(int a, int b, int n) {
    if (n == 3) {
        return a + b;
    } else {
        return fib(b, a+b, n-1);
    }
}

Answer 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
   }
}

由于每个print something都是O(1),算法的时间复杂度将取决于我们运行该行的次数.好吧,正如你的TA提到的那样,我们通过查看这种情况下的组合来做到这一点.内环将运行(N +(N-1)+ ... + 1)次,总共(N + 1)*N/2.

由于我们忽略常数,我们得到O(N ²).

现在,对于更棘手的案例,我们可以获得更多数学.尝试创建一个函数,其值表示算法运行所需的时间,给定输入的大小为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^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

(我们可以尝试做类似的事情以证明下限)

在大多数情况下,对函数的最终运行时进行很好的猜测将使您能够通过感应证明轻松解决重现问题.当然,这需要你能够先猜测 - 只有很多练习可以帮助你.

最后一点,我想指出一下Master定理,这是我现在可以想到的更常见的复杂问题的唯一规则.当你必须处理一个棘手的分而治之的算法时使用它.

另外,在你的"if case"例子中,我会通过欺骗和分割成两个独立的循环来解决这个问题.t里面有一个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算法示例所示

Answer 2

通常,决定算法复杂性在理论上是不可能的.

然而,实现它的一个很酷且以代码为中心的方法实际上只是直接考虑程序.举个例子:

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次.而现在我们看到,计数器加ñ正好ñ倍,所以我们简化了这:

int counter = 0;
counter += n * n;

我们出现了(正确的)O(n ²)复杂性:)它在代码中:)

让我们看一下递归Fibonacci计算器的工作原理:

int fib(int n) {
  if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

更改例程,使其返回在其中花费的迭代次数,而不是实际的Fibonacci数:

int fib_count(int n) {
  if (n < 2) return 1;
  return fib_count(n - 1) + fib_count(n - 2);
}

它仍然是斐波那契!:)所以我们现在知道递归Fibonacci计算器具有复杂度O(F(n)),其中F是Fibonacci数本身.

好的,让我们看看更有趣的东西,比如简单(和低效)的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;
}

我们现在可以看到实际上from和to的绝对值不再重要,而只是它们的距离,所以我们将其修改为:

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是要排序的数组的大小,因此你有复杂性M(x)的重现(这在第二行显而易见:)

M(x) = 2(M(x/2) + x)

而这需要解决才能获得封闭的表格解决方案.通过猜测解M(x)= x log x,您可以做到最简单,并验证右侧:

2 (x/2 log x/2 + x)
        = x log x/2 + 2x
        = x (log x - log 2 + 2)
        = x (log x - C)

并验证它是否渐近等效于左侧:

x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x