Big O表示法运行时
我已经获得了一些代码来解决他们的大O运行时间，有人可以告诉我，我是否在正确的轨道上？
//program1 int i, count = 0, n = 20000; for(i = 0; i < n * n; i++) { count++; } 是O（n ^ 2）？
//number2 int i, inner_count = 0, n = 2000000000; for(i = 0; i < n; i++) { inner_count++; }
这是一个O（n）？
//number3 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { count++; } }
为O（n ^ 2）？
//number4 for(i = 0; i < n; i++) { for(j = 0; j < i; j++) { for(k = 0; k < j; k++) { inner_count++; } } }
是O（n ^ 3）？
//number5 int i, j, inner_count = 0, n = 30000; for(i = 0; i < n; i++) { for(j = 0; j < i; j++) { inner_count++; } }
那是一个O（n ^ 3）？
//number6 int i, j, k, l, pseudo_inner_count = 0, n = 25; for(i = 0; i < n; i++) { for(j = 0; j < i*i; j++) { for(k = 0; k < i*j; k++) { pseudo_inner_count++; for(l = 0; l < 10; l++); } } }
非常困惑这一个O（n ^ 3）??
//number7 int i, j, k, pseudo_inner_count = 0, n = 16; for(i = n; i > 1; i /= 2) { for(j = 0; j < n; j++) { pseudo_inner_count++; for(k = 0; k < 50000000; k++); } }
上）？ （随着他们越来越难，我越来越迷茫）
//number8 int i, j, pseudo_inner_count = 0, n = 1073741824; for(i = n; i > 1; i /= 2) { pseudo_inner_count++; for(j = 0; j < 50000000; j++); }
为O（n ^ 2）？
还有一个我没看到，完全不知道{
int i, wrong_count = 0, n = 200; for(i = 0; i < square(n); i++) { wrong_count++; } printf("%d %d\n", wrong_count, square(wrong_count)); return 0; } int square(int m) { int i, j = 0; for(i = 0; i < m * m; i++) { j++; } return j; }
如果有人能够澄清这些并帮助我更好地理解它们，我将非常感激。
- number5是O（N ^ 2）
- number6是O（N ^ 6）
- number7是O（N * logN）
- number8是O（logN）
其余似乎是正确的。
尝试了解作为N的函数完成了多少操作，所有常量操作，例如
for (int i = 0; i < 333333333; ++i) { j++; }
事实上是O（1）
number5 = O（n ^ 2） – 第二个循环从1变为小于n的数，包括n，因此它基本上是1..n或O（n）。
number6 = O（n ^ 6） – 第二个循环是n ^ 2，第三个循环是n ^ 3（n * n ^ 2）。 第四个内循环是O（1）所以它不算数。
number7 = O（n log n） – 第一个循环是O（log2（n））（因为你继续将索引除以2），第二个循环是O（n）1..n，内循环是再次O（1）因为它不依赖于n。
number8 = O（log n） – 与上述相同的原因。
其余的都很好。
如果我的快速跟踪正确，您对5,6,7和8的答案是不正确的。
下面是8的痕迹
1: int i, j, pseudo_inner_count = 0, n = 1073741824; 2: 3: for(i = n; i > 1; i /= 2) 4: { 5: pseudo_inner_count++; 6: for(j = 0; j < 50000000; j++); 7: }
因此，第5行是一个基本的操作，因此O（1）与第3行中的检查和赋值相同。第6行看起来像是一个大的东西，但因为它总是将是50000000，所以它是一个恒定的时间操作O（1）也让我们考虑这个shell：
1: int i, j, pseudo_inner_count = 0, n = 1073741824; 2: 3: for(i = n; i > 1; i /= 2) 4: { 5: }
我不是免费做某人的功课，但我会完成这一项，减少i的方法是两个分区的意思，它将需要log_2操作达到1，给出O的运行时间（ log（n））