我無法理解 while 回圈如何影響 Big O 時間復雜度。
例如，我將如何計算下面代碼的時間復雜度？因為它有一個遍歷陣列中每個元素的 for 回圈和兩個嵌套的 while 回圈，所以我最初的想法是 O(n^3) 的時間復雜度，但我認為這是不對的。
HashMap<Integer,Boolean> ht = new HashMap<>();
for(int j : array){
if(ht.get(j)) continue;
int left = j-1;
//check if hashtable contains number
while(ht.containsKey(left)){
//do something
left--;
}
int right = j 1;
//check if hashtable contains number
while(ht.containsKey(right)){
//do something
right ;
}
int diff = right - left;
if(max < diff) {
//do something
}
}
uj5u.com熱心網友回復：
有最好的情況、一般的情況和最壞的情況。
我將不得不假設有一些東西限制了兩個while回圈，因此它們的迭代次數都不超過n次數，n陣列中元素的數量是多少。
在最好的情況下，你有 O(n)。那是因為if(ht.get(j))總是true，continue路徑總是被選擇。兩個while回圈都沒有執行。
對于最壞的情況，if(ht.get(j))is always false，while回圈將被執行。此外，在最壞的情況下，每個while回圈都會n通過。[1] 兩個內部回圈的最終結果是 2 * n 乘以外部回圈的 n ： (2 * n) * n。這會給你 O(n^2) 的時間復雜度。[2]
查找時間可能是一個因素。哈希表查找通常在恒定時間內運行：O(1)。那是最好的情況。但是，最壞的情況是 O(n)。當所有條目具有相同的哈希碼時，就會發生這種情況。如果發生這種情況，它可能會將最壞的情況更改為 O(n^3)。
[1] 我懷疑最壞的情況，第一個while回圈的通過次數加上第二個while回圈的通過次數實際上n或接近它。但是，這并不會改變結果。
[2] 在大 O 中，我們選擇了增長最快的項，而忽略了系數。所以，在這個例子中，我們把2.2*n*n
uj5u.com熱心網友回復：
假設您的和中分別有m和n條目。HashMaparray
由于您有回圈的n元素for，因此復雜性可以寫為n * complexity_inside_for.
在for回圈內部，您有兩個連續（非嵌套）while回圈，每個回圈都具有復雜性，m因為在最壞的情況下，它需要遍歷HashMap. 因此，complexity_inside_for = m m = 2m。
所以總的來說，時間復雜度是n * 2m. 然而，當mandn接近無窮大時，這個數字2并不重要，因為它不是m和/或的函式，n并且可以被丟棄。這給出了一個大 O 時間復雜度O(m*n)
uj5u.com熱心網友回復：
對于一個嵌套回圈，時間復雜度是這樣的：O(n^2)。
在 i 的每次迭代中，內部回圈執行“n”次。回圈的時間復雜度等于最里面的陳述句要執行的次數。
所以對于你的情況，這將是 O(n^2) O(n)。
在那里你可以找到更多解釋
時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/481508.html
上一篇：如何使用for回圈列印偶數？