循環插入排序

Question

這是關於插入排序的分析在「算法簡介」一書中的分析。它說，下面的for循環執行N（=則爲a.length）時間：

for j = 2 to A.length 
.... 

誰能告訴我爲什麼這個循環執行n次，而不是N-1次？

感謝， Ganesh神

Answer 1

我找到了答案我自己：

對於環路J = 2〜5

第一次迭代：j被設置爲2，循環條件計算爲真。

第二次迭代：j遞增爲3，循環條件計算結果爲真。

第3次迭代：j增加到4，循環條件計算結果爲真。

第4次迭代：j增加到5，循環條件計算結果爲真。

第5次迭代：將j遞增爲6，並且循環條件評估爲false，並退出循環。

所以for語句被執行5次，儘管循環內的語句被執行了4次。

Answer 2

在分析運行時間的算法是一般的做法是圓的東西了。如果N更大，那麼1不會有所作爲。只對樣本空間巨大的問題進行算法分析。如果您想對具有200萬整數的數組進行排序，該怎麼辦？如果循環運行1,999,999次，那麼它會有什麼不同嗎？因此，如果循環運行N-1次或N + 1次是N.我希望我說清楚。

Answer 3

你的書大概說它在O(n)時間執行，而不是n次。它可能還包含算法運行時分析和O-notation中的一章（您可能已跳過）。長話短說，在漸近分析常數無關緊要：O(cn+k) = O(n)，其中c和k是常數。

Answer 4

你的意思是O（N）還是說它只會n次。在估算運行時間時，如果運算量很大，運行一百萬次或一百萬次減去一次，可以採用相同的方式進行概括。因此，運行n-1次的東西大約需要運行n次的東西。

Answer 5

假設數組索引是基於1的（本書使用這種約定的AFAIR），那麼循環執行n-1次。但是，在算法複雜性方面，對於最壞情況分析（大哦），通常會將事情進行四捨五入（取消恆定的乘法器/加法器）。我相信這本書說O（n）而不是n。