我的問題是 O(n^2) 與 O(ab) 之間的區(qū)別是什么。嵌套的 for 循環(huán)中有兩個(gè)不同的 N 數(shù)組。從 CTCI 中，我讀到它不是 O(N^2) 而不是 O(ab)，因?yàn)樗胁煌妮斎?。for (int i = 0; i < arrayA.length; i++) { for (int j = 0; j < arrayB.length; j++) { }}
4 回答
慕的地8271018
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
很簡單的：
因?yàn)樽鲱愃?(a) 1 x (b) 1000 萬……只需要 1000 萬個(gè)“時(shí)隙”。
而 (n) 1000 萬 x (n) 1000 萬……好吧，那總是 n*n，不是嗎。
換句話說：O(ab) 表示您有兩個(gè)決定復(fù)雜性的參數(shù)。O(n^2) 表示您的復(fù)雜性僅取決于一個(gè)參數(shù)。
翻翻過去那場雪
TA貢獻(xiàn)2065條經(jīng)驗(yàn) 獲得超14個(gè)贊
為什么 O(n^2) 與 O(ab) 不同？
O(n^2)轉(zhuǎn)化為O(n*n)，其復(fù)雜度僅取決于 1 個(gè)變量。您的示例取決于 2 個(gè)獨(dú)立變量，因此復(fù)雜性不一定是這兩個(gè)變量中的任何一個(gè)的二次方。例如，如果您有一個(gè)非常小b和一個(gè)非常高的a，那么您的復(fù)雜度幾乎與 a 成線性關(guān)系。
這兩個(gè)表達(dá)式相等的唯一情況是 when n = a = b, thenO(n^2) = O(a*b)將適用。
catspeake
TA貢獻(xiàn)1111條經(jīng)驗(yàn) 獲得超0個(gè)贊
因?yàn)樗Q于應(yīng)用程序/輸入的屬性。
如果 a 或 b 保持較低或恒定，則 O(ab) 的縮放比例類似于 O(n) 而不是 O(n^2)。
添加回答
舉報(bào)
0/150
提交
取消