使用大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