我有一個嵌套的for回圈:
for(i = 0; i < n*n; i )
for(j = 0; j <= i/5; j )
print("Hello World!")。
我怎樣才能找到這個回圈的時間復雜性。
我在想，對于外回圈，它從0運行到n^2（獨占），所以它運行了n^2 1次。
對于內回圈，它取決于i，這是我迷失的地方。有什么指點嗎？
uj5u.com熱心網友回復：
幾乎所有的情況下，你都可以直接插入常識告訴你的包含最壞情況的數字。除非所說的最壞情況保證只運行固定數量的次數而不考慮N（即所有的回圈都是接近最優的，除了最多五個回圈不是，即使我們回圈了一千次--非常罕見）--那么就用最壞情況來計算。
這也適用于每個單獨的回圈。為每個回圈取最壞的情況。這是正確的，除非回圈之間存在聯系，例如，如果內回圈只有在某些外回圈保證運行最佳情況下才會運行 "最壞情況"，反之亦然--當存在明顯的關系時。
因此，讓我們在這里應用它：
- i從0到n*n運行，這部分很簡單。
- j從0到i（我們可以忽略常數因素，所以
/5部分是不相關的，我們可以忘記它）。
j回圈的最壞情況是，i等于n*n，這使得j從0運行到n*n。所以我們就用這個方法吧。
這其實是一個很好的例子。
這實際上是正確的答案；這是一個運行n*n迭代的回圈（這是j回圈），這個程序被重復n*n次（i回圈），總復雜度為O(n^4)（哎喲，隨著n的增長，這將很快被推翻）。
如果你不確定數學運算是否可行，請嘗試找到線性。這可以保證它。在這種情況下，最好的情況是當i為0時，在這種情況下j回圈只運行一次，而最壞的情況是j回圈運行n*n次。重要的是，j回圈的特性是線性的。在i回圈的 "生命周期 "中，只需繪制出j回圈性能的圖表，這就是一個簡單的直線關系。前5個j回圈運行一次，后5個j回圈運行兩次，一直到最后一個j回圈運行n*n/5次。
所有 j 回圈的'平均值'就是這條線的中間：n*n/5的一半。這就是n*n/10，而常數因素并不重要，所以這仍然是n*n。因此，為什么這是O(n^4)，與for (j = 0; j < n*n; j )會是一樣的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/321074.html
標籤：
上一篇：javascript試圖將一個數字陣列轉換為鍵值，然后是與鍵值相匹配的指數。
下一篇：用一個回圈來代替if陳述句？