algorithm - 循环中的大 O 复杂性

Question

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

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

非常感谢任何形式的帮助/第二意见:)

Answer 1

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

(n - 2) + (n - 4) + ... + 2(或末尾的奇数)

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

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