算法运行时间中的对数

yuyang911220

【1】分析算法最混乱的方面大概集中在对数上面， 除分治算法外，可将对数最常出现的规律概括为下列一般法则：1.1）如果一个算法用常数时间（O(1)）将问题的大小削减为其一部分（通常是1/2），那么该算法就是 O（logN）；
1.2）如果使用常数时间只是把问题减少一个常数（如将问题减少1），那么这种算法就是 O（N）；
【2】下面，我们提供具有对数特点的3个荔枝：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; 不是必须的。为什么？自己去想其中的原因；（去掉后，运行结果完全一样）；