我有一個關於在插入排序算法中使用二進制搜索的簡單問題。更確切地說，在通常插入排序的每一步中，我們只是在該排序的子數組中使用二進制搜索來查找元素所屬的位置，而不是線性比較元素與前一個（已排序）子數組中的所有元素。我知道這減少了算法所做比較的次數（O（log n）而不是O（n）），但是每個步驟所需的交換次數仍然佔優勢，複雜度仍然是O（n^2）。二進制插入排序和複雜性
我也知道複雜性不是很容易與運行時間相關。我試圖比較n（數組大小）的「小」值的兩種算法的運行時間，高達約500000.二進制插入排序總是比通常的插入排序更快。
兩個都是O（n^2）的事實告訴我，當n變得足夠大時，運行時間應該是相似的，對吧？在這種情況下，有什麼「足夠大」的想法可以看到類似的運行時間？
兩個都是O（n^2）的事實告訴我，當n變得足夠大，運行時間應該是相似的，對嗎？
小心 - 這是不正確的。 n^2和2n^2永遠不會接近在一起，因爲n變得更大;他們分開得更遠。但都是O(n^2)。
這是什麼意思，那麼，說你的算法都是O(n^2)？那麼，這意味着最終每個人都可以以n^2的某個常數倍數爲界。對於您的二進制插入排序，它可能是10n^2，而對於您的標準插入排序，它可能是1000n^2。兩者都是n^2，雖然效率可能相差100（在本例中）。
複雜性告訴你更多關於某個特定函數的行爲，而不是關於該函數如何與其他函數疊加起來。例如，如果你知道你的函數是O(n^2)，你知道對於n,f(n+1)的較大值，f(n+1)將增長不超過某些常數時間n + 1（爲什麼？因爲n^2的派生值是2n，線性，它告訴你連續項之間的差異線性增長）。
這是一個很好的解釋，它肯定有助於澄清我的誤解。 – dbluesk
理論上二進制插入排序的複雜度是O（log_2（n！））， Wolframalpha。
這實際上在O（n 2）和O（n log（n））之間，更接近於O（n log（n））。
並不意味着n越大，運行時間應該是相似的。這只是意味着當n接近無窮大時，兩者將以大致相同的速率接近無限的運行時間。 –