iT邦幫忙

2021 iThome 鐵人賽

DAY 5
0
自我挑戰組

30天不怕演算法:白話文版系列 第 5

Day 05:到底有多壞?演算法的最壞情況執行時間

討論演算法的執行時間到現在,我們只提最糟糕的情況,好像不斷在強調演算法的效能可以有多差。

你可能會想,就算用線性搜尋玩猜數字,最衰最衰要猜100次,那也會有很多不用猜到100次的情況,或甚至猜一次就中的情況耶,不用考慮那種可能性嗎?

在分析演算法時,通常會討論最壞情況的執行時間,一方面是因為比較好掌握——最壞情況的數字比較不會因為輸入的內容而變動;另外一方面也等於是不對輸入做任何的預設或限制。也就是即便在輸入最大、最亂、最難操作的情況,執行時間最慢也不會慢於大O執行時間,大O時間即是上限。也因為不對輸入有任何限制,最壞情況適合不特定主題或情境的開放討論。

當然除了最壞情況外,還有別種分析演算法的方式,像是平均情況(average-case)的執行時間或針對特定輸入的執行時間,但這些通常代表對於輸入已有一些預設,例如當開發者已經很清楚某個問題會有哪些常見或典型的輸入,這類的分析可能就會特別有用。

另外也有最佳情況(best-case)執行時間,用大Ω符號(big Omega notation)表達,代表演算法需要最少步驟的情況。例如像線性搜尋和二分搜尋最快都可以一次就找到,所以它們的最佳情況執行時間都是Ω(1)。


上一篇
Day 04:大O符號的含意
下一篇
Day 06:選擇排序(selection sort)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言