我的問題是 O(n^2) 與 O(ab) 之間的區別是什么。嵌套的 for 循環中有兩個不同的 N 數組。從 CTCI 中，我讀到它不是 O(N^2) 而不是 O(ab)，因為它有不同的輸入。for (int i = 0; i < arrayA.length; i++) { for (int j = 0; j < arrayB.length; j++) { }}
4 回答
慕的地8271018
TA貢獻1796條經驗 獲得超4個贊
很簡單的：
因為做類似 (a) 1 x (b) 1000 萬……只需要 1000 萬個“時隙”。
而 (n) 1000 萬 x (n) 1000 萬……好吧，那總是 n*n，不是嗎。
換句話說：O(ab) 表示您有兩個決定復雜性的參數。O(n^2) 表示您的復雜性僅取決于一個參數。
翻翻過去那場雪
TA貢獻2065條經驗 獲得超14個贊
為什么 O(n^2) 與 O(ab) 不同？
O(n^2)轉化為O(n*n)，其復雜度僅取決于 1 個變量。您的示例取決于 2 個獨立變量，因此復雜性不一定是這兩個變量中的任何一個的二次方。例如，如果您有一個非常小b和一個非常高的a，那么您的復雜度幾乎與 a 成線性關系。
這兩個表達式相等的唯一情況是 when n = a = b, thenO(n^2) = O(a*b)將適用。
添加回答
舉報
0/150
提交
取消