循环中的大 O 复杂性

Question

如果你有一个带有循环的算法，第一次执行 n 步，然后第二次执行 n − 2 步，下一次执行 n − 4 步，并不断重复直到最后一次执行循环 2步骤，这个循环的复杂度是多少？

我相信这表现出 O(n^2) 的复杂性，因为未执行的步骤数呈二次方增长。我很难想象这样的循环本身，这让我对自己的答案不太自信。

任何类型的 help/second 意见都将不胜感激:)

Answer 1

你是正确的，复杂度是 Θ(n²)。这是因为你描述的是 arithmetic progression:

(n - 2) + (n - 4) + ... + 2（或最后一个奇数）

（显然，2 + 4 + 6 + ... + (n - 2) 或奇数开头的等价物，顺便说一句）。

使用formula for the sum，它是第一个和最后一个元素的平均值乘以元素的数量。每一项都是 Θ(n)，它们的乘积是 Θ(n²)。