问题是:
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。
最佳答案
由于允许您使用大 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
关于algorithm - 使用大 O 表示法计算算法的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30521532/