运行时间的对数

前言：在进行算法分析时，时间复杂度有O(n)，O(n2)，O(n3)对所有输入元素进行O（1）操作，利用两层循环进行O(1)操作，等。这些时间复杂度可以直观理解，然而遇到O(log(n))和O(nlog(n))时便有些摸不着头脑，为此《数据结构与算法分析》专门举了三个例子来说明。由于欧几里得运算，没怎么看懂而且不是很重要就不写了。

例一、二分查找

描述：给定一个整数X和整数A0，A1，。。。，An-1，后者已经预先排序并在内存中，求使得Ai=X的下标i，如果X不在数据中，则返回i=-1.

分析：如果一个算法利用常数时间O(1)将问题缩减为一部分（通常为1/2），那么该算法就是O(log(n))。另一方面，如果该算法只是减少了一个常数，那么就是O(n)。本算法对照上述法则，high-low=N-1 变为 high-low= -1，循环内部每一次花费O(1)且high-low减小一半。

例二、幂运算

描述：对X的N次方进行运算。

分析：最为简单的算法是，进行X的N-1次自乘，则时间复杂度为O(n)。高效率的算法则是运用两个数学等式，X的n次方=X的1/2 n次方×X的1/2 n次方（n为偶数），X的n次方=X×X的（n-1）/2次方×X的（n-1）/2次方。

结语：对于时间复杂度为O(log（n）)可以认为利用常数时间操作O(1）将原始问题缩小为几分之一。而对于O(nlog(n))就是将问题分为几个部分分别解决然后将结果综合起来。