我不明白第二个循环是如何有O（i ^ 2）的？

Question

第二个循环从i运行到i ^ 2 -1所以没有。 of times = i ^ 2 - i + 1

function(int n) {

外部运行n次

    for (int i = 0; i < n; i++) {
        for (int j = i; j < i * i; j++) {
            if (j % i == 0) {

这运行了j次

                for (int k = 0; k < j; k++) {
                    printf("*");
                }
            }
        }
    }
}

Answer 1

所以不行。 of times = i ^ 2 - i + 1

如果i变大，例如非常大，那么i^2和i都变得非常大。然而，i^2的增长速度比i快，那么与i的增加相比，i^2的增加可以忽略不计。对于Big-O notation的time complexity，这表示为O（i ^ 2）。

此外，它是“O”（字母O），而不是“0”（数字零）。

Answer 2

你会在这里找到答案

for (int j = i; j < i * i; j++) {

j正在运行到i ^ 2（或i * i），这导致内部循环的O（i ^ 2）

Answer 3

你说的是因为内环从i到i²，复杂性不能是O（i²）。 复杂性确实最多为O（i²）但是：

1. 对于i = 1，第二次循环执行1次
2. 对于i = 10,90次（距离100不太远）
3. 对于i = 100,9900次（距离10000不太远）
4. 对于i = 1000,999000次（距离1M不太远）

每当你乘以一个数字n（在我的情况下为10）时，内部循环的运行次数将超过n²次。这表明复杂性至少为O（i²）。

结论：复杂性正是（=最多+至少）O（i²）

---

复杂性的一般知识：

您将看到的大多数代码都具有以下有序列表中的复杂性，或者它们的组合（稍后将详细介绍）： n^0 (= constant) < log2(n) < sqrt(n) < n < n^2 < exp(n)

复杂性是一个仅适用于非常大的数字的术语。 这与小值无关，例如你会看到here。

在你的情况下，具有非常大的价值，i²在i面前铺天盖地，所以O(i²-i) = O(i²)。

更一般地说，复杂性只会倍增：

• 你的外环是O(n)
• 你的内环是O(n^2)
• 结果：您的代码示例是O(n^3)

显然，当你结合复杂性时，订单将保持不变。 例如，我之前的有序列表乘以O(n)将变为： n < n*log2(n) < n*sqrt(n) < n^2 < n^3 < n*exp(n)

如您所见，感谢前一个列表中n和n ^ 2之间的值。