算法的复杂性

Question

以下是翻译：

这个问题的时间复杂度被给定为O(n)。难道不应该是O(n^2)吗？因为外部循环是O(n)，内部循环也是O(n)，所以 n*n = O(n^2)？

这个问题的答案说明是O(n)，这怎么可能呢？

public static void q1d(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n; j++) {
            count++;
        }
    }
}

以下问题的复杂度为O(n^2)，你是如何得出这个结论的？可以有人详细解释一下吗？

public static void q1E(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        count++;
        for (int j = 0; j < n/2; j++) {
            count++;
        }
    }
}

谢谢

- Harminder

---

我认为上面的是O(n^2)。你对下面的有什么疑问？ - WordsWorth

这意味着我的教授提供的答案是不正确的。 - Harminder

看起来答题卡上有错误。 - Zohaib

Answer 1

第一个例子是O(n^2)，所以看起来他们犯了一个错误。为了计算（非正式地）第二个例子，我们可以进行 n * (n/2) = (n^2)/2 = O(n^2)。如果这不太清楚，那么你需要重新学习一下O(n^k)的含义。

- Yuushi

Answer 2

这两段代码的复杂度都是O(n*n)

第一段

外层循环运行了n次，内层循环从0到n-1运行不等的次数

所以

总计 = 1 + 2 + 3 + 4 ... + n

如果你加上等差数列，就是 n * ( n + 1 ) / 2，时间复杂度为O(n*n)

第二段

外层循环运行了n次，内层循环从0到n-1/2运行不等的次数

所以

总计 = 1 + 1/2 + 3/2 + 4/2 ... + n/2

如果你加上等差数列，就是 n * ( n + 1 ) / 4，时间复杂度也是O(n*n)

- parapura rajkumar

---

那么如果 n/2，它仍然等于 O(n) 吗？但内部循环的迭代只有外部循环的一半，这会有任何影响吗？ - Harminder

@user1085135: O(n) 的意思是 线性。不管它乘以什么常数，唯一重要的是它是线性的。 - zerkms

Answer 3

第一个情况肯定是O(n^2)

第二个也是O(n^2)，因为在计算大O时省略常数。

- zerkms

Answer 4

你的答案有误，第一个算法显然是O(n^2)。

大O符号表示的是“最坏情况”，因此在计算大O值时，通常会忽略常数的乘除。

话虽如此，你的第二个例子在最坏情况下也是O(n^2)，因为尽管内部循环只有“半个”n，但n仍然是明显的边界因素。实际上，第二个算法的操作次数将少于O(n^2)——但是，大O符号旨在衡量算法在n趋近于无穷大时的行为，而不是关注确切的操作次数。

- debracey

---

第二个算法不会低于O(n^2)，它恰好是O（n^2）。 我怀疑你并不清楚“O(n^2)”的实际含义。 它意味着当n趋近于无穷大时，算法的运行时间对于n的两个值而言，其增加量与这些n值之间的差平方成比例。 - David Schwartz

不，在实践中，算法的实际时间复杂度将略小于O(n^2)。然而，因为大O是一个上限，我们说它是O(n^2)。您正确指出n/2因子显然由n界定--正如我在我的答案中所示。还有其他边界测量方法（即大Theta），其计算边界因子不同。 - debracey

你为什么认为算法的实际时间复杂度会小于O(n^2)？我认为它将恰好是O(n^2)，因为该算法的复杂度恰好符合O(n^2)的定义。如果它不是恰好的O(n^2)，那么就没有什么是恰好的了。我们之所以说它是O(n^2)，是因为它确实是O(n^2)。当这一点绝对清晰明了时，你似乎想要使其模糊、混乱和不精确。 - David Schwartz

因为实际复杂度是O(n^2) + C，其中C是某个常数。在这种情况下，C是负数。因此它将略微小于直接的n^2。C是微不足道的，但你仍然应该将“答案”写成O(n^2) - C。 - debracey

复杂度为 O(n^2) + C 的意思与复杂度为 O(n^2) 完全相同。 - David Schwartz

Answer 5

两者都是O(n^2)。你的答案是错误的。或者你可能把问题写错了。

- Shashwat