算法运行时间中的对数

0.1） source code and text description are from data structure and alg analysis ；

1.1）如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分（通常是1/2），那么该算法就是 O（logN）；
1.2）如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是 O（N）；

Example1）二分查找（对分查找）
这里写图片描述

源代码（此算法成立的前提是 M>=N）：
https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p22.c
算法分析（Analysis）：
- A1）显然，每次迭代在循环内的所有工作花费为O（1），因此分析需要确定循环的次数；循环从 high-low=N-1开始并在 high-low >=-1 时结束；
- A2）每次循环后high – low 的值至少将该次循环前的值减半；于是，循环的最多次数为 | log(N-1) |（向上取整）+2；
- A3）举个例子：若high-low =128，则在各次迭代后 high – low 的最大值为 64、32、16、8、4、2、1、0、-1；因此运行时间为 O（logN）；

Example2）欧几里得算法——计算两数的最大公因数

两个整数的最大公因数（greatest common divisor）：它是同时整除二者的最大整数，如GCD（50,15）=5；
源代码： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p23.c
时间复杂度： T(N) = O (logN)
算法解说（Description）
- D1）算法通过连续计算余数直到余数为0为止，最后的非零余数就是最大公因数；
- D2）可以证明，在两次迭代后，余数最多是原始值的一半。（这点特别重要）；
- D3）迭代次数至多是2logN=O (logN)；
引申出一个定理：如果 M > N , 则 M mod N < M / 2 。（余数是小于除数N的，记住这一点）

Example3）幂运算

Attention：我们用乘法的次数作为运行时间的度量；
源代码： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/blob/master/chapter2/p24.c
时间复杂度： T(N)=O (logN) ；
代码演示分析步骤
算法解说（Description）：
- D1）如计算X^62，用到了9次乘法而不是62次乘法：
- D2）显然，所需要的乘法次数最多是 [ 2 * logN（向下取整） -1]；
- D3）实际上，源代码中的 if(N == 1) return x; 不是必须的。为什么？自己去想其中的原因；（去掉后，运行结果完全一样）；