complexity-theory - 如何使用步数计算时间复杂度

Question

sum(array,n)
{
  tsum=0;
  for(i=0;i<n;i++)
    tsum=tsum+array[i];
  return tsum;
}

Answer 1

就big-O而言，这与处理的数组元素的数量成正比，所以 O(n)

（注意，您的代码覆盖了 i 参数，假设该参数旨在为 n，以指示要求和的数组元素的数量？）

Answer 2

您在 1 步中声明 tsum=0，然后运行循环 n 步。在每次迭代中，你做一个 1 步的总和，然后你在 1 步中返回 tsum。您的步数约为：

1 + 3n + 1，就忽略常数和所有低阶项（如果它们的数量恒定）而言，这是 O(n) 的大哦符号。每次迭代有 3n 个步骤，你增加变量 i，检查它是否小于 n，然后进入循环进行计算。

Answer 3

                                Cost         Times
tsum=0;                         c1             1
for(i=0;i<n;i++)                c2             n+1
    tsum=tsum+array[i];         c3             n
return tsum;                    c4             1

算法总成本为 1*c1 + (n+1) c2 + n c3 + 1*c4

因此，该算法所需的时间与 n 成正比。