【0】README

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

---

【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; 不是必須的。為什么？自己去想其中的原因；（去掉后，運行結果完全一樣）；

總結

以上是生活随笔為你收集整理的算法运行时间中的对数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。