目前，我正在攻讀計算機科學課程的期末考試。其中一個問題就是如何結合運行時間的問題，所以我舉一個例子。需要幫助學習跑步時間
我想知道，如果我創建了一個程序，使用插入排序對輸入進行預處理，然後使用二進制搜索搜索值「X」，我將如何組合運行時間來查找最佳，最差和平均情況整體計劃的時間複雜性？
例如...
插入排序
最壞情況爲O（n^2）
最佳案例爲O（n）
平均情況爲O（n^2）
二進制搜索 最壞情況Ø （logn）時間
最佳案例O（1）
平均情況O（logn）時間
會最壞的情況下是爲O（n^2 + logn）時間，或者這將是爲O（n^2），或都不是？
最好的情況是O（n）嗎？
平均情況是O（nlogn），O（n + logn），O（logn），O（n^2 + logn）還是沒有一個？
我傾向於過度思考解決方案，所以如果我可以得到任何關於組合運行時間的指導，將不勝感激。
非常感謝。
您通常不會將運行時間「組合」在一起，以確定整體效率等級，而是將每個最差，平均和最佳情況的時間花費最長。因此，如果您要執行插入排序，然後在數組中找到元素X之後執行二進制搜索，最壞的情況是O（n^2），最好的情況是O（n） - - 全部來自插入排序，因爲它需要最長的時間。
好，太好了。爲了確保我正確地關注你，無論輸入集合的大小或x的搜索次數如何，這都是真的嗎？ – 2011-04-22 20:28:34
但整個案件的運行時間取決於進行了多少次搜索。如果少於n^2次搜索，則總體時間肯定與n^2成正比。但是，如果執行無限次搜索，則整體運行時間爲O（M log n），其中「M」是搜索次數。所以可以說排序和搜索的分期運行時間是O（M log n）。 – 2011-04-22 21:08:34
@Jim Mischel非常感謝！我只是想知道你有哪些知識？在這種情況下，我想假設搜索的數量遠大於輸入的數量。 – 2011-04-22 22:21:18
根據我有限的研究，（我們還沒有達到攤銷所以這可能是其中吉姆其餘正確的），但基本上你只是根據誰是最慢的整體算法去。
這似乎是對算法的主題一本好書（我沒有什麼可比較）： http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1303528736&sr=8-1
還有麻省理工學院有關於這裏他們的網站的算法進行全程是鏈接爲此呢！ http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/
我已經發現它很有幫助，它可能不會明確回答你的問題，但我認爲它會幫助你更有信心地看到一些主題解釋了幾次。
也許另一個角度幫助：http://eternallyconfuzzled.com/arts/jsw_art_bigo.aspx – sehe 2011-04-22 20:42:20