使用大O符号

Question

这里的问题计算算法的运行外环具有1+n+1+n运行时间，第二个循环具有n*(1+n/2+1+n/2)运行时间，以及第三条语句有n*n/2运行时间。第二和第三种说法让我非常困惑，我不知道我的计算是否正确，任何澄清将不胜感激，谢谢advnace。

Answer 1

由于您可以使用Big-O符号，因此您不必记下所有的详细信息。

设T（n）为输入大小为n时算法的运行时间。

首先，puts("hello")是O（1）。从代码中可以清楚地看到，puts("hello")已执行少于n^2次。还要注意的是，如果外环改变（减小）到

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

内环将为至少n/2次，每次i被执行，这意味着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)）。

如果你有问题了解大O和西塔的概念，您可以参考以下视频：https://youtu.be/6Ol2JbwoJp0