《算法技术手册》一2.4.8 指数级算法性能

2.4.8 指数级算法性能

考虑有一种锁，它由3个连续的数字拨盘组成，每个拨盘包含0~9的数字，并且都可以独立设置10个数字中的一个。假如你发现了这种锁，并且没有能将其打开的数字组合。你可能认为这不过是耗费一些体力工作的问题，只要尝试从000~999的1000种组合中可能的每一种即可。为了归纳这个问题，假定锁有n个表盘，那么总的可能性总数为10n。用穷举方法解决这个问题被认为是指数级性能或者O(10n)，这个例子以10作为基数，但是更常见的指数底数一般是2。不过，对于任意的基数b（b> 1）,它们的性能都是指数级。
指数级算法仅仅对于一些非常小的n值较为实用。某些算法虽然最坏情况下的性能是指数级，但是它们在平均情况下性能表现良好，因此在实际情况中仍然被大量使用。使用单纯性（simplex）算法解决线性规划问题就是一个很好的例子。