algorithm - 当我们使用 for 循环对 n 个数求和时 **ex.for(i=1;i<=n;i++)**

Question

当我们对 n 求和时使用 for 循环的数字 for(i=1;i<=n;i++)这个的复杂度是 O(n)，但是如果我们使用算术/几何级数级数 n(n-1)/2 的公式进行同样的计算那个时候如果我们计算时间复杂度，它是 O(n^2)。如何 ？请解决我的疑问。

Answer 1

您对数字所代表的内容感到困惑。

当我们谈论复杂性时，基本上我们是在计算步骤的数量。

n(n+1)/2 是 Summation(1..n) 的答案，这是正确的，但不同的方法采用不同的 steps 数来计算它，我们正在计算这些步骤的数量。

比较以下内容:

int ans = 0;
for(int i=1; i<=n;i++) ans += i;
// this use n steps only

int ans2 = 0;
ans2 = n*(n+1)/2;
// this use 1 step!!

int ans3 = 0;
for(int i=1, mx = n*(n+1)/2; i<=mx; i++) ans3++;
// this takes n*(n+1)/2 step
// You were thinking the formula would look like this when translated into code!

所有三个答案给出相同的值!

所以，你可以看到只有第一种和第三种方法(当然是根本不实用)受n的影响，不同的n会导致它们采取不同的步骤，而使用公式的第二种方法，无论 n

是什么，总是采取 1 步

也就是说，如果你事先知道公式，直接用公式计算答案总是最好的