条件为假的 for 循环的大 O

Question

对于这个 Big O 问题，我只需要一些说明或帮助。我不知道我是否解释正确，但我注意到 for 循环有一个错误条件，所以这意味着它根本不会循环。我的教授说仍然可以确定循环的运行时间。所以我在想的是：

1 + (n - 1 - n) * (n) = 1 + 1 * n = 1 + n = O(n)

说明：1为循环外操作。 (n - 1 - n) 是外循环的迭代，n 是内循环的迭代。

注：我还在学习Big O，所以如果我的逻辑有任何错误，请指正。

int total = 0;
for (int i = n; i < n - 1; i++) {
    for (int j = 0; j < n; j++) {
        total = total + 1
    }
}

Answer 1

Big O分析中不应该有任何负数。对于负运行时间没有意义。此外，(n - 1 - n) 不仅仅是 O(1) 的顺序。您的外循环甚至不会进入一次迭代。因此，循环中任何语句的时间复杂度都无关紧要。

总结一下，运行时间是1 + 1 = O(1)。

Answer 2

用于描述函数渐近行为的大 O 符号。基本上，它告诉您函数增长或增长的速度拒绝

例如，在分析某些算法时，可能会发现完成大小为 n 的问题所需的时间（或步数）由

给出

T(n) = 4 n^2 - 2 n + 2

如果我们忽略常量（这是有道理的，因为它们取决于程序运行所在的特定硬件）和增长较慢的项，我们可以说 "T(n)" 以 n^ 的顺序增长2 " 和 write:T(n) = O(n^2)

对于正式定义，假设f(x) 和g(x) 是定义在实数的某个子集上的两个函数。我们写

f(x) = O(g(x))

（或 f(x) = O(g(x)) for x -> infinity 更精确）当且仅当存在常数 N 和 C 使得

|f(x)| <= C|g(x)| for all x>N

直觉上，这意味着 f 的增长速度并不比 g

如果a是实数，我们写

f(x) = O(g(x)) for x->a

当且仅当存在常数 d > 0 和 C 使得

|f(x)| <= C|g(x)| for all x with |x-a| < d

所以对于你的情况，它是 O(n^2) 作为 |f(x)| > C|g(x)|

引用自http://web.mit.edu/16.070/www/lecture/big_o.pdf

int total = 0;
for (int i = n; i < n - 1; i++) { // --> n loop
    for (int j = 0; j < n; j++) { // --> n loop
        total = total + 1; // -- 1 time 
    }
}

}

Big O Notation 给出了一个假设，当值非常大时，外循环将运行 n 次，而内循环是运行ning n 次

假设 n -> 100 比总数 n^2 10000 运行次

条件为假的 for 循环的大 O

Big O of a for loop with a false condition

java

big-o