本篇文章學習數列求和的一些方法。這些方法對后面學習算法的時間復雜度非常有幫助。

文章目錄

• • 1. 數列求和公式
  • • 1.1 二分搜索的時間復雜度求解
  • 2 估計和式上屆的放大法
  • 3 估計和式漸近的界
  • 4 總結

1. 數列求和公式

下面這幾個數列求和公式都是高中學過的公式。

• 等差、等比數列和調和級數

下面給出一個求和的例子，使用了一些高中都會的變換的技巧：

學習上面的公式，主要是為了解決算法的時間復雜度，下面以二分搜索的時間復雜度為例，講解如何利用上面的公式求解出，時間二分搜索的時間復雜度（關于時間復雜度的概念，可以參看以前的文章：【算法設計與分析】03 算法及其時間復雜度）。

1.1 二分搜索的時間復雜度求解

• 假設二分數組為T[n]，要搜索的數為：x。如下圖是一個簡單數組的搜索過程。

上述的二分搜索最終并沒有找到要搜索的元素的位置。所以二分搜索的數據的輸入情況，可以分為兩種，一種是想要搜索的數x在數組中，一種是想要搜索的x不在數組中，那么一共就有2n+1中情況發生。如下圖：

• 左邊是x在數組中，可以在任何一個位置出現，有n種情況。
• 右邊是x不在數組中，那么x出現在數組的兩邊或者在數組中兩個元素的中間，就有n+1種情況
• 所以一共有2n+1種輸入情況。
  

注意：上述，假設n=2^k-1,只是為了方便后面的計算。

現在已經知道了總的輸入，還需要知道總的輸入對應的比較的次數，才能計算出時間復雜度。
由分析可以看出，比較t次的輸入的個數為：

所以：

• 對于t= 1，2…k-1，比較t次的輸入有 ：2^t-1 個 (這個對應的是x在數組中的情況)
• 對于x不在數組中的情況，需要比較的次數是k，那么比較k次的輸入就是：2^k-1+n+1個。（式子中的n+1是對應的不在數組中非空隙的個數，2^k-1 對應的是x在數組中的情況，因為就算要找的數不在數組中，也要將數組比較完全一遍才能夠知道）

那么總次數就等于：對每個輸入乘以這個輸入對應的次數并求和

假設n=2^k-1 ，各種輸入的概率相等，則二分搜索平均時間復雜度為A（n）：

上述的計算過程用到了一開始學習的幾個公式以及變換技巧，自己慢慢掌握。

上述的計算結果大家都不陌生了，正式二分搜索的平均時間復雜度：logn

2 估計和式上屆的放大法

放大法在高中大家學的都很熟練應該。

• 放大法：

• 放大法的例子

3 估計和式漸近的界

以下方法用到了基本微積分的概念。

求上屆

求下屆

上面的上屆和下屆都是同一個級別的，所以：

4 總結

本文學習了序列求和的基本公式：

• 等差數列
• 等比數列
• 調和級數

對于無法計算的序列和，可以采用放大法求上屆，用積分做和式漸近的界

這些基本的計算方法對計數循環過程的基本運算次數很有幫助。也就是算法的時間復雜度了。

總結

以上是生活随笔為你收集整理的【算法设计与分析】08 序列求和的方法的全部內容，希望文章能夠幫你解決所遇到的問題。

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