我的代碼段的運行時分析是否正確？

我試圖分析這個代碼段 enter image description here

要分析這個問題，我看到，外環將要執行N/C倍。然後每當外層循環運行時，內層循環也會執行n/c次。因此，總的來說，如果您放棄常數，此分段將運行n^2/c^2或O（n^2）。

是否還有一種視覺方式可以做到這一點，類似於（從http://courses.cs.washington.edu/courses/cse373/15wi/lectures/lecture3.pdf）幻燈片19？我嘗試這樣做，但得到（C *（N）（N + 1））/ 2，我不知道是正確的。

enter image description here

是有一個辦法。 – 2015-02-07 02:49:21

@ I.K。請賜教:)，你只是用C乘以每一項？ – committedandroider 2015-02-07 03:34:50

隨着'n'變大，'n^2'在'（c *（n）（n + 1））/ 2'中做出最大的貢獻，所以你可以放棄其他的一切。 – August 2015-02-07 04:26:39

對於這個問題，這裏怎麼會分析它現在

最倍外環將運行是^Ñ ⁄ _Ç和用於每次外部循環運行的迭代器，所述內迴路也將運行至多^Ñ ⁄ _Ç倍。

因此該算法的最壞的情況下大O運行時是O（^Ñ ⁄ _Ç）或爲O（n ）

2015-03-22 20:28:49 committedandroider

（C *（N）（N + 1））/ 2

= C *（N^2 + N）/ 2

=（C/2）× （N^2 + N）

下降常量和保持n的最高權力賦予的O最終答案（N^2）

2015-02-07 02:53:02 spyr03

是啊，只是最後一部分不等於n^2/c^2。我認爲這不重要，是嗎？ – committedandroider 2015-02-07 03:34:17

回答