*只有一個峰
我正在學習的教科書說當m = n時貪婪上升演算法的時間復雜度為O（nm）和O（n ^ 2）。所以這意味著在最壞的情況下，我必須訪問二維陣列的所有元素。
但我認為這種情況只有在行或列為 1 并且元素已排序時，所以如果我選擇最小元素，我必須訪問所有元素才能達到峰值。
那時，我無法理解，當n = m時，時間復雜度為O（n ^ 2）。
如果n = m = 1，則需要O（1），但是說O（n ^ 2）是沒有意義的。
在 n=m 和 n>1 的另一種情況下，是否可以采用 O(n^2)？如果沒有這些，那么 O(n^2) 不是正確的復雜性嗎？
我認為 O(n m) 可能是正確的復雜度，因為最壞的情況是起點為 (0,0) 且峰值位于 (n,m) 時。所以要達到頂峰，我必須垂直移動 n 時間，水平移動 m 時間。
我哪里理解錯了？
*我的問題的重點是，我認為基于 O(nm) 將 n=m 情況下的復雜性定義為 O(n^2) 是錯誤的。正確的復雜度是 O(n m)=O(2n)=O(n)
uj5u.com熱心網友回復：
您可以輕松地構建一個至少需要訪問n*m/2元素的案例：將最大值放在右下角，然后沿著曲折的路徑，在每個遍歷的空間上放置一個略小于前一個元素的元素。路徑一直向左，然后向上兩個，然后一直向右，依此類推，直到到達左上角或右上角。在所有其他空間中放置一個最小元素。
對于n=m=4，它看起來像這樣：
0 0 0 1
5 4 3 2
6 0 0 0
7 8 9 10
如果您碰巧選擇了1，則需要遍歷10 > n*m/2元素。
對于n=4和m=5：
1 2 3 4
0 0 0 5
9 8 7 6
10 0 0 0
11 12 13 14
在這里，您需要遍歷14 > n*m/2元素。
所以在最壞的情況下，這是O(n*m/2) = O(nm).
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520453.html
標籤：算法时间复杂度