algorithm - Summation(n) Theta(n^2) 根据其公式如何计算，但 Theta(n) ij 我们只是将其视为单个 for 循环？

Question

我们的教授和各种资料都说 Summation(n) = (n) (n+1)/2，因此是 theta(n^2)。但直觉上，我们只需要一个循环就可以找到前 n 项的总和!所以，它必须是 theta(n)。我想知道我在这里错过了什么？!

Answer 1

所有这些答案都误解了问题，就像原来的问题一样:重点不是衡量整数求和算法的运行时复杂度，而是讨论如何推理复杂度一种算法，在 1..n 中的 i 的每次传递期间采取 i 步骤。考虑插入排序:在每一步 i 插入原始列表的一个成员输出列表是 i 个元素长，因此它需要 i 步骤(平均)执行插入。插入排序的复杂度是多少？它是所有这些步骤的总和，或者是 1..n 中 i 的 i 的总和。这个总和是 n(n+1)/2 其中有一个 n^2，因此插入排序是 O(n^2)。