我開始閱讀“算法簡介，第三版”這本書，我遇到了一些對我來說不夠清楚的東西，關(guān)于“插入排序”算法。請先看一下圖片：首先，作者定義了 n = A.length。 A.length是數(shù)組 A 的長度。因此，假設(shè)數(shù)組“A”的長度為 5。如果我從 j = 2（如圖所示）到 A.Length = 5 運(yùn)行for循環(huán)，我會說第一行將運(yùn)行 4 次，這意味著對于任何 n，它將運(yùn)行 n - 1 次。另一方面，作者寫道，第一行將運(yùn)行 n 次。我錯過了什么？
2 回答
MMMHUHU
TA貢獻(xiàn)1834條經(jīng)驗 獲得超8個贊
第一行可能是指檢查條件的次數(shù)。如果您的循環(huán)運(yùn)行n-1次數(shù)，則檢查迭代器上的條件n（包括最后，當(dāng)它變?yōu)榧贂r）。n-1正如預(yù)期的那樣，在循環(huán)體內(nèi)，所有語句都已標(biāo)記為 。
慕碼人8056858
TA貢獻(xiàn)1803條經(jīng)驗 獲得超6個贊
這個 n 可能表示插入排序具有的外部 for 循環(huán)的時間復(fù)雜度 -> O(n^2)，而不是它的實際循環(huán)計數(shù)。
添加回答
舉報
0/150
提交
取消