这段代码的 Big-O 复杂度是多少？

Question

的大 O 是什么

void fun(int n) {
   for(i=1; i<=n; i=i+2) { }
}

我的答案：O(log n)（因为 i 值是 1,3,5,7,9 整体减少 2）

void fun(int n) {
    for(i=1; i<=n; i=i+2) { }
}

我的答案：O(log n)，因为这是二次方（我认为）。

void fun (int n) {
    for (i=1; i<=n; i++) {
        for(j=1;j<=n;j++) { }

        for(k=1;k<=n;k++) { }
     }
}

我的回答：O(n^3)，因为循环必须在 i.

内专门针对 j 和 k 执行一个循环

请说明。

Answer 1

大O符号的正式定义是

f(x) ∈ O(g(x)) as there exists c > 0 (e.g., c = 1) and x0 (e.g., x0 = 5) such that f(x) < cg(x) whenever x > x0.

从你的思路来看，你似乎不明白，如果有一个常数可以乘以g(x)使得f(x)总是小于或等于g(x)，f (x) 并不比 g(x) 大一个数量级。

以下是大 O 解决方案：

(1) O(n)。 O(n/2) 是 O(n)

(2) O(n) 因为这与 (1)

相同

(3) O(n^2) 因为内层循环运行s 2 * n 次外层循环的每次迭代，即运行s n 次。因此运行是 2 * n * n 即 O(n^2)

Answer 2

O(n)：即使将处理的值数量增加了一半，这仍然与 n 成正比。比较 n、n/2 和 log n:
的这些图

您可以看到 n/2 与 n 成正比（总是恰好一半，即它偏离 常数因子），而 log n 的增加速度明显更慢.

在大 O 表示法中，常数因子被忽略，即 O(2n) = O(n)，因为当 n 非常大时，2 与 n 相比微不足道。
假设您在第二个示例中的意思可能是 for(i=1;i<=n;i=i*2)，这实际上是 O (log n)，因为您正在检查呈指数增长的值（1、2、4、8、16，...），所以 i 最多会加倍 log n达到 n 之前的次数。例如，如果 n = 16，则 i 将翻倍 4 次（如上例所示），并且 4 = log₂ 16.
O(n²) 由于内循环运行s 2n次，而外循环运行s n次，所以每次内循环迭代都是O(n)，所以当外循环是运行 n 次时，总复杂度是 O(n²).

通常，如果您有许多嵌套循环，每个嵌套循环都从 0 到 n（可能有一些常数因子），估计代码时间复杂度的一种快速方法是计算循环嵌套的深度.然后，假设每个最内层循环迭代执行 constant-time 操作（例如，递增数字，访问数组索引），总时间复杂度将为 n^k，其中 k 是嵌套循环的数量。这适用于您的示例 3，它有 2 层循环嵌套（即使最内层有两个循环一个接一个，这只是增加了一个常数因子）。

Answer 3

第一个是O(n)。是的，您跳过了一半的循环周期，但这意味着对于每个 n，您循环 n/2 次并且 O(n/2) 与 O(n) 相同。

第二个看起来和第一个一样，但我假设你的意思是：

for (i = 1; i < n; i=i*2)

}

是的，那是 O(log n)

第三个可能会让您感到困惑，因为它给人的印象是三重嵌套循环，但实际上不是，两个内部循环嵌套在第一个循环上，所以它实际上是 O(n*(n+n )) = O(n*2n) = O(2n^2) 最后是 O(n^2)

Answer 4

void fun(int n){
    for(i=1;i<=n;i=i+2){;}
}

循环示例：

i:    1   3   5   7   9   11   13   15   ...

The loop iterates approximately n/2 times, which is in O(n).

void fun(int n){
    for(i=1;i<=n;i=i*2){;}
}

示例循环将经过：

i:    1   2   4   8   16   32   64   128   ...

That is not quadratic. That is exponential. It loops approximately log(n) times (to the base of 2, but it does not really matter here), and thus it is in O(log(n)).

二次（2 次多项式）为

i:    1   4   9   16  25   36  49  64  ...

试着看看这两者之间的区别，指数开始较慢，但随着 i 的增长而增长得更快。

void fun(int n){
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){;} // O(n)
        for(k=1;k<=n;k++){;} // O(n)
    }
}

两个内循环分别执行n次，即2*n步

The outer loop is executed n times. In each step the two inner loops are executed. Which make in total n * 2 * n, which is in O(n^2).

这段代码的 Big-O 复杂度是多少？

What is the Big-O complexity of this code?

big-o

time-complexity