使用大 O 表示法计算算法的运行时间

Question

这里是问题：

for(i=1;i<=n,i++){

      for(j=2*i;j<=n,j++){

        puts("hello"):
       }
}

这是我的解决方案：外循环有 1+n+1+n 运行ning 次，第二个 for 循环有 n*(1+n/2+1+n/2)运行次，第三个语句有 n*n/2 运行次。第二个和第三个陈述让我很困惑，我不知道我的计算是否正确，任何澄清将不胜感激，谢谢advnace。

Answer 1

由于允许您使用大 O 表示法，因此您不必写下所有细节。

令 T(n) 为当输入大小为 n 时算法的运行时间。

首先，puts("hello")是O(1)。从代码中可以清楚地看到，puts("hello") 被执行了不到 n^2 次。另请注意，如果将外循环更改（减少）为

for (i = 0; i < n / 4; ++i)

内循环每i次至少执行n/2次，也就是说语句puts("hello")至少执行n/4 * n/2 = n^2/8次。

现在如上所述，我们有 n^2/8 <= T(n) <= n^2。因此我们有 T(n) = O(n^2)（分析很严密，这意味着我们有 T(n) = \Theta(n^2)）。

如果您对 Big-O 和 Theta 的概念有困难，可以参考这个视频：https://youtu.be/6Ol2JbwoJp0

Calculate the Runtime of an Algorithm using Big-O Notation