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

Question

问题是:

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

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

        puts("hello"):
       }
}

这是我的解决方案:外循环有 1+n+1+n 运行时间，第二个 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