《算法技術手冊》一2.4.8 指數級算法性能

考慮有一種鎖，它由3個連續的數字撥盤組成，每個撥盤包含0~9的數字，并且都可以獨立設定10個數字中的一個。假如你發現了這種鎖，并且沒有能将其打開的數字組合。你可能認為這不過是耗費一些體力工作的問題，隻要嘗試從000~999的1000種組合中可能的每一種即可。為了歸納這個問題，假定鎖有n個表盤，那麼總的可能性總數為10n。用窮舉方法解決這個問題被認為是指數級性能或者O(10n)，這個例子以10作為基數，但是更常見的指數底數一般是2。不過，對于任意的基數b（b> 1）,它們的性能都是指數級。

指數級算法僅僅對于一些非常小的n值較為實用。某些算法雖然最壞情況下的性能是指數級，但是它們在平均情況下性能表現良好，是以在實際情況中仍然被大量使用。使用單純性（simplex）算法解決線性規劃問題就是一個很好的例子。