算法的運(yùn)行時(shí)間以不同的速度增加
“算法的運(yùn)行時(shí)間以不同的速度增加”這句話應(yīng)該如何理解呢？下面我們通過(guò)例子來(lái)看看這句話到底想表達(dá)什么。
小明現(xiàn)在需要編寫(xiě)一個(gè)查找算法，這個(gè)算法服務(wù)于學(xué)校圖書(shū)館，目的是幫助童鞋們能夠快速的找到自己需要的書(shū)籍所在位置。
假設(shè)小明現(xiàn)在只會(huì)“二分查找”和“簡(jiǎn)單查找”。一方面，二分查找的速度很快，小明必須在 10 秒鐘內(nèi)找到書(shū)籍所在位置，否則童鞋們沒(méi)有更多耐心等待。另一方面，簡(jiǎn)單查找算法編寫(xiě)起來(lái)更容易，因此出現(xiàn) bug 的可能性更小。
為了檢驗(yàn)這兩種算法的耗時(shí)，小明決定計(jì)算兩種算法在列表包含 100 個(gè)元素的情況下需要的時(shí)間。
假設(shè)檢查一個(gè)元素需要 1 毫秒。使用簡(jiǎn)單查找時(shí)，小明必須檢查 100 個(gè)元素，因此需要 100 毫秒才能查找完畢。而使用二分查找時(shí)，只需檢查 7 個(gè)元素（log2 100大約為7），因此需要 7 毫秒就能查找完畢。然而，實(shí)際要查找的列表可能包含 10 億個(gè)元素，在這種情況下，簡(jiǎn)單查找需要多長(zhǎng)時(shí)間呢？二分查找又需要多長(zhǎng)時(shí)間呢？
小明使用包含 10 億個(gè)元素的列表運(yùn)行二分查找，運(yùn)行時(shí)間為 30 毫秒（log2 1 000 000 000大約為30）。他心里想，二分查找的速度大約為簡(jiǎn)單查找的 15 倍，因?yàn)榱斜戆?100 個(gè)元素時(shí)，簡(jiǎn)單查找需要 100 毫秒，而二分查找需要 7 毫秒。因此，列表包含 10 億個(gè)元素時(shí)，簡(jiǎn)單查找需要 30 × 15 = 450 毫秒，完全符合在 10 秒內(nèi)查找完畢的要求。小明決定使用簡(jiǎn)單查找。這是正確的選擇嗎？
不是。實(shí)際上，小明錯(cuò)了，而且錯(cuò)得離譜。列表包含 10 億個(gè)元素時(shí)，簡(jiǎn)單查找需要 10 億毫秒，相當(dāng)于 11 天！為什么會(huì)這樣呢？因?yàn)槎植檎液秃?jiǎn)單查找的運(yùn)行時(shí)間的增速不同。
| 簡(jiǎn)單查找 | 二分查找 | 元素個(gè)數(shù) |
| 100 毫秒 | 7 毫秒 | 100 |
| 10 秒 | 14 毫秒 | 10 000 |
| 11 天 | 30 毫秒 | 1 000 000 000 |
隨著元素?cái)?shù)量的增加，二分查找需要的額外時(shí)間并不多，而簡(jiǎn)單查找需要的額外時(shí)間卻很多。因此，隨著列表的增長(zhǎng)，二分查找的速度比簡(jiǎn)單查找快得多。小明以為二分查找速度為簡(jiǎn)單查找的 15 倍，這不對(duì)：列表包含 10 億個(gè)元素時(shí)，為 3300 萬(wàn)倍。有鑒于此，僅知道算法需要多長(zhǎng)時(shí)間才能運(yùn)行完畢還不夠，還需知道運(yùn)行時(shí)間如何隨列表增長(zhǎng)而增加。這正是大O表示法的用武之地。
大O表示法指出了算法有多快。例如，假設(shè)列表包含 n 個(gè)元素。簡(jiǎn)單查找需要檢查每個(gè)元素，因此需要執(zhí)行 n 次操作。使用大O表示法，這個(gè)運(yùn)行時(shí)間為 O(n)。單位秒呢？沒(méi)有！大O表示法指的并非以秒為單位的速度。大O表示法讓你能夠比較操作數(shù)，它指出了算法運(yùn)行時(shí)間的增速。
大O表示法指出了最糟糕情況下的運(yùn)行時(shí)間
假設(shè)你使用簡(jiǎn)單查找在電話簿中找人。你知道，簡(jiǎn)單查找的運(yùn)行時(shí)間為 O(n)，這意味著在最糟情況下，必須查看電話簿中的每個(gè)條目。如果要查找的是 Chars ——電話簿中的第一個(gè)人，一次就能找到，無(wú)需查看每個(gè)條目?？紤]到一次就找到了 Chars，請(qǐng)問(wèn)這種算法的運(yùn)行時(shí)間是 O(n)還是 O(1) 呢？
簡(jiǎn)單查找的運(yùn)行時(shí)間總是為 O(n)。查找 Chars 時(shí)，一次就找到了，這是最佳的情形，但大O表示法說(shuō)的是最糟的情形。因此，你可以說(shuō)，在最糟情況下，必須查看電話簿中的每個(gè)條目，對(duì)應(yīng)的運(yùn)行時(shí)間為 O(n)。這是一個(gè)保證——你知道簡(jiǎn)單查找的運(yùn)行時(shí)間不可能超過(guò) O(n)。
說(shuō)明
除最糟情況下的運(yùn)行時(shí)間外，還應(yīng)考慮平均情況的運(yùn)行時(shí)間，這很重要。
一些常見(jiàn)的大O運(yùn)行時(shí)間
下面按從快到慢的順序列出了你經(jīng)常會(huì)遇到的5種大O運(yùn)行時(shí)間。
O (log n )，也叫對(duì)數(shù)時(shí)間 ，這樣的算法包括二分查找。
O (n )，也叫線性時(shí)間 ，這樣的算法包括簡(jiǎn)單查找。
O (n * log n )，這樣的算法包括快速排序——一種速度較快的排序算法。
O (n 2 )，這樣的算法包括選擇排序——一種速度較慢的排序算法。
O (n !)，這樣的算法包括旅行商問(wèn)題的解決方案——一種非常慢的算法。
暫無(wú)評(píng)論，快來(lái)評(píng)論吧!