对数

一般地，如果a(a＞0，a≠1)的b次幂等于N，就是ab=N，那么数b叫做以a为底N的对数（Logarithm），记作logaN=b，其中a叫做对数的底数，N叫做真数。

从定义可知，负数和零没有对数。事实上，因为a＞0，所以不论b是什么实数，都有ab＞0，这就是说不论b是什么数，N永远是正数，因此负数和零没有对数。

编程人员经常使用对数，它有两个用途。第一，许多程序需要对一些对象进行编码，那么表示n个编码至少需要多少位呢？答案是⌈log2n⌉。例如，如果要存储1000个不同的编码，至少需要⌈log21000⌉=10位（10位可以产生1024个不同的可用编码）。第二，对数普遍用于分析把问题分解为更小子问题算法。在一个线性表中查找指定值所使用的折半查找算法就是这样一种算法。折半查找算法首先与中间元素进行比较，以确定下一步是在上半部分进行查找还是在下半部分进行查找。然后继续将适当的子表分半，直到找到指定的值（折半查找算法在8.2.3小节有详细的描述）。一个长度为n的线性表被促逐次分半，直到最后的子表中只有一个元素，一共需要进行多少次呢？答案是log2n次。

在以后的实例中用到的对数几乎都以2为底，这是因为数据结构和算法总是把事情一分为二，或者用二进制位来存储编码。