資料結構與算法分析基本術語 2021.3.21
- 1、基本術語
- 2、資料
-
- 2.1 資料的邏輯結構
- 2.2 資料的存儲結構
-
- 2.2.1 順序存儲
- 2.2.2 連結存儲
- 2.2.3 索引存儲
- 2.2.4 散列存儲
- 3、算法分析
-
- 3.1 算法分析舉例
1、基本術語
雖然計算機具有非常廣泛的應用領域，可以用于科學計算、情報檢索、企業管理等，但它的核心功能概括起來卻隻有一個：處理資料。但計算機處理的資料絕不是雜亂無章的，而是有着某種内在聯系的，隻有厘清楚資料的内在聯系并合理地組織資料，才能對它們進行有效的管理和存儲。
2、資料
計算機科學中，資料的含義極其廣泛：一切能夠輸入到計算機中并被計算機成U型處理的資訊，包括文字、表格、圖像等，都成為資料。
結點（資料元素）是組成資料的基本機關，在計算機程式中通常把結點作為一個整體進行考慮和處理。
一般情況下，一個結點中含有若幹個字段（資料項），字段是構成資料的最小機關。
結點與結點之間的邏輯關系成為資料的邏輯結構。
資料在計算機中的存儲表示成為資料的存儲結構，如磁盤上的檔案、記憶體中的數組等。
資料結構并沒有公認的标準定義，但把某種邏輯關系組織起來的一組結點，按一定的存儲方式存儲于計算機中，并在其上定義了一個運算的集合，稱為一個資料結構。
資料類型作為進階程式設計語言中的一個基本概念，與資料結構的概念密切相關。一方面，在程式設計語言中，每一個資料都屬于某種資料類型。類型明顯或隐含地規定了資料的取值範圍、存儲方式以及允許進行的運算，是以資料類型是在程式設計語言中已經實作了的資料結構。另一方面，在程式設計過程中，當需要引入某種新的資料結構時，必須借助程式設計語言所提供的資料類型來描述資料的存儲結構。
2.1 資料的邏輯結構
在大多數情況下，資料的邏輯結構可以用二進制組 S = ( D , R ) S=(D,R) S=(D,R)來表示。其中，D是結點的有限集合；R是結點有序對的集合，表示D上的一種關系。例如，二進制組list=(D,R1),tree=(D,R2)和graph=(D,R3)分别描述了具有5個結點的三種不同的邏輯結構，其中
D = { a , b , c , d , e } D=\{a,b,c,d,e\} D={a,b,c,d,e} R 1 = { < a , b > , < b , c > , < c , d > , < d , e > } R_{1}=\{<a,b>,<b,c>,<c,d>,<d,e>\} R1={<a,b>,<b,c>,<c,d>,<d,e>} R 2 = { < a , b > , < a , c > , < b , d > , < b , e > } R_{2}=\{<a,b>,<a,c>,<b,d>,<b,e>\} R2={<a,b>,<a,c>,<b,d>,<b,e>} R 3 = { < a , b > , < a , c > , < d , a > , < e , c > } R_{3}=\{<a,b>,<a,c>,<d,a>,<e,c>\} R3={<a,b>,<a,c>,<d,a>,<e,c>}
對于任意一個邏輯結構 S = ( D , R ) S=(D,R) S=(D,R)，若 a ∈ D ， b ∈ D a\in D，b \in D a∈D，b∈D， < a , b > ∈ R <a,b> \in R <a,b>∈R，則稱a是b的前驅，b是a的後繼；若某結點沒有前驅，則稱該結點為開始結點；若某結點沒有後繼，則稱該結點為終端節點。例如，在list結構中，a是開始結點，e是終端節點；在tree結構中，a是開始結點，c、d、e是終端節結點；在graph結構中，d和e是開始結點，b和c是終端結點。
資料的邏輯結構可分為線性結構和非線性結構兩大類。線上性結構中，開始結點和終端結點都是唯一的，除了開始結點和終端結點以外，其餘結點都有且僅有一個前驅，有且僅有一個後繼。非線性結構又可以細分為樹形結構和圖狀結構兩類。在樹形結構中，每個結點最多隻有一個前驅，但可以有多個後繼，可以有多個終端結點。在圖狀結構中，每個結點的前驅和後繼的數目都可以是任意的，是以可能沒有開始結點和終端節點，也可能有多個開始結點、多個終端結點。在上述的三個執行個體中，list屬于線性結構，tree屬于樹形結構，graph屬于圖狀結構。
除二進制組外，資料的邏輯結構還有其他表示方法。例如，對于非線性結構，通常采用圖示法；用小圓圈表示結點，在圈内或圈外附近标注結點名稱或數值，用帶箭頭的弧線表示結點之間的關系。下圖所示的是上例的邏輯結構tree和graph。
對于線性結構，可以用一個帶括号的結點序清單示之。例如，list結構可簡單地表示為（a,b,c,d,e）。在實際應用中，資料的邏輯結構可能會非常複雜，為了有效地對資料進行處理，必須首先搞清楚資料的邏輯結構，對資料進行合理的組織。
2.2 資料的存儲結構
資料在計算機中的存儲既要求存儲各結點的數值，又需要存儲結點與結點間的邏輯關系。在實際的應用當中，可根據問題規模（通常是指結點數目的多少）和運算種類等因素适當選擇，這裡将介紹四種基本的存儲結構：順序存儲、連結存儲、索引存儲和散列存儲。
2.2.1 順序存儲
順序存儲是把邏輯上相鄰的結點存儲在一組連續的存儲單元中，其結點之間的邏輯關系由存儲單元位址間的關系隐含表示。假定每個結點占用一個存儲單元，資料從200号單元開始由低位址向高位址方向存放，則線性結構執行個體lis D = { a , b , c , d , e } D=\{a,b,c,d,e\} D={a,b,c,d,e}t的順序存儲結構如下圖所示：
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | c | d | e |
順序存儲結構
順序存儲的主要優點是節省存儲空間，因為配置設定給資料的存儲單元全用于存放結點的數值，結點之間的邏輯關系沒有占用額外的存儲空間。用這種方法來存儲線性結構的結點時，可實作對各結點的随機通路。這是因為線性結構中每個結點都對應一個序号（開始結點的序号為1，它的後繼結點的序号為2，…），可以根據結點的序号i，計算出結點的存儲位址
L o c ( i ) = q + ( i − 1 ) × p Loc(i) = q + ( i - 1) \times p Loc(i)=q+(i−1)×p
其中，p是每個結點所占單元數；q是第一個節點所占單元的首位址。
順序存儲的主要缺點是不便于修改，在對結點進行插入、删除運算時，可能要移動一系列的結點。例如，要删除list結構中的第3個結點c，使list結構由(a,b,c,d,e)變成(a,b,d,e)。删除操作則必須将結點d和e往左移動一個單元，操作結果如下圖(a)所示；或者将結點a和b往右移動一個單元，操作結果如下圖(b)所示。移動結點的目的是要保證在進行了删除操作後，剩餘結點仍然占用一片連續的存儲單元。
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | d | e |
（a）後面的結點往前移
| 200 | 201 | 202 | 203 | 204 |
|---|---|---|---|---|
| a | b | d | e |
（b）前面的結點往後移
2.2.2 連結存儲
連結存儲是給每個結點附加指針字段，用于存放相鄰結點的存儲位址。假定給執行個體list中的每個結點附加一個“後繼指針”字段，用于存放後繼結點的首位址，則可得到如圖（a）所示的list連結存儲表示。圖中，每個結點占用兩個連續的存儲單元，一個存放結點的數值，另一個存放後繼結點的首位址。
連結存儲的主要優點是便于修改，在進行插入、删除運算時，僅需要修改結點的指針字段值，不必移動結點。例如，在圖(a)所示的連結存儲結構上，若要實作删除操作，使list結構由（a,b,c,d,e）變成(a,b,d,e)，則隻要将207号單元的内容由202改為208即可。操作結果如圖(b)所示。若要實作插入操作，使list結構由(a,b,c,d,e)變成(a,x,b,c,d,e)，則首先在存儲器中找到兩個連續的空單元，假設這兩個空單元的位址是100号和101号，然後将x存入新結點的數值字段（100号單元）中，将結點b的存儲單元首位址206存入新結點的指針字段（101号單元）中，最後将新結點的存儲單元首位址100存入結點a的指針字段（201号單元）中，操作結果如圖（c）所示。
與順序存儲方法相比，連結存儲的主要缺點是存儲空間的使用率較低，因為配置設定給資料的存儲單元有一部分被用來存放結點之間的邏輯關系了。另外，由于邏輯上相鄰的節點在存儲器中不一定相鄰，是以，在用這種方法存儲的線性結構上不能對結點進行随機通路。
2.2.3 索引存儲
索引存儲是根據結點的序号确定結點的存儲位址，具體做法是：建立索引表和節點表；将各結點的數值按任意順序存放在節點表中，而将每個結點的存儲位址（即在節點表中的位置）用順序存儲方法存入索引表中。對于線性結構來說，各結點的存儲位址在索引表中是按結點的序号依次排列的。圖（a）是list的一種索引存儲表示。
線性結構采用索引存儲後，可以對結點進行随機通路。在進行插入、删除運算時，由于隻需移動存儲在索引表中的結點的存儲位址，而不必移動存儲在結點表中的結點的數值，是以仍可保持較高的運算效率（這是因為，在一般情況下，結點中總包含有多個字段，移動一個節點的數值要比移動一個結點的位址花費更多的時間）。
如果要在上圖所示的索引存儲結構上實作删除操作，使list結構由(a,b,c,d,e)變成(a,b,d,e)，則隻需将結點c的存儲位址202從索引表中删除即可，操作結果如圖（b）所示。
2.2.4 散列存儲
散列存儲是根據結點的值确定結點的存儲位址，具體做法是：以結點中某個字段的值為自變量，通過某個函數（稱為散列函數）計算出對應的函數值，再把i當作結點的存儲位址。假定list結構中5個節點的數值是下列5個字元串：‘Wuhan’、‘Nanjing’、‘Shanghai’、‘Xian’、‘Beijing’。選用函數
L o c ( k e y ) = a s c ( l e f t ( k e y , 1 ) ) m o d 8 Loc(key)=asc(left(key,1)) mod 8 Loc(key)=asc(left(key,1))mod8來計算結點的存儲位址，其中，asc(left(key,1))表示取字元串key中第一個字元的ASCII碼，mod是取模運算，計算結果如下：
| key | Wuhan | Nanjing | Shanghai | Xian | Beijing |
|---|---|---|---|---|---|
| asc(key) | 87 | 78 | 83 | 88 | 66 |
| Loc(key) | 7 | 6 | 3 | 2 |
于是，可以得到下圖所示list的散列存儲表示。
| Xian | Beijing | Shanghai | Nanjing | Wuhan |
|---|
0 1 2 3 4 5 6 7
散列存儲結構 散列存儲的優點是查找速度快，隻要給出待查找結點的數值，就有可能立即算出結點的存儲位址。 與前三種存儲方法不同的是，散列存儲方法隻存儲結點的數值，不存儲結點與結點之間的邏輯關系。散列存儲方法一般隻用于要求對資料能夠進行快速查找、插入的場合。 采用散列存儲的關鍵是要選擇一個好的散列函數和處理“沖突”的辦法。 在用進階語言程式設計時，可以用程式設計語言所提供的資料類型來描述資料的存儲結構。例如，用“一維數組”表示一組連續的存儲單元，來實作順序存儲結構、索引存儲結構和散列存儲結構；用C++語言中的“指針”來實作連結存儲結構。 ## 2.3 資料的運算 資料的運算是資料結構的一個重要研究内容，它和資料的邏輯結構、存儲結構有着密切的聯系。資料的各種運算都是在邏輯結構上定義的，但具體的實作要在一定的存儲結構上進行。在不同的應用場合，會對資料有各種各樣的運算要求，常見的運算包括：**查找**、**插入**、**删除**和**排序**。資料運算用**算法**來表示，算法是一個和**程式**非常相似的概念，二者的主要差別在于：==程式一定要用程式設計語言書寫==，而==算法則不必（例如，算法可以是一個流程圖）==。 - 1）查找 * 在資料結構中查找數值字段等于給定值的結點。 - 2）插入 * 在資料結構中适當位置插入一個新結點。 - 3）删除 * 從資料結構中删除某個結點。 - 4）排序 * 重新排列線性結構中各結點的邏輯順序。
3、算法分析
對于資料的任何一種運算，如果資料的存儲結構不同，則其算法描述一般是不相同的，即使在存儲結構相同的情況下，由于可以采用不同的求解政策，往往也可以有許多不同的算法，一般來說，好的算法應具有如下四個特征：
- (1) 正确：算法必須滿足問題的要求，對合法的輸入能産生問題要求的輸出結果；對非法的輸入能作出适當的反應或處理。
- (2) 可讀：算法是給人看的，其可讀性有助于人們對算法的了解，一個晦澀難懂的算法易于隐藏錯誤，而且難以調試和修改。
- (3) 運作時間較短。
-
(4) 占用較少的存儲空間。
在這裡，算法分析不是分析算法是否正确或是否容易閱讀，而是分析算法執行過程中所需的時間和存儲空間。算法的執行時間和所需的存儲空間主要與問題規模有關。問題規模是一個和輸入有關的量，例如向量的長度、矩陣的階數等，可以說算法的執行時間和所需的存儲空間都是問題規模的函數，進行算法分析就是要找出這種函數關系。由于在大多數情況下，算法在執行過程中所需的最大存儲空間是容易估算的，是以算法分析主要是分析算法執行時間與問題規模之間的關系。
算法的執行時間等于算法中各語句執行時間的總和，而某個語句的執行時間等于該語句執行一次所需時間與執行次數的乘積。然而，在大多數情況下，精确統計算法中每個語句的執行次數和執行一次所需的時間都是非常困難的，為了分析的友善，算法的執行時間通常表示成數量級的形式：
T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))
其含義為：當問題規模n足夠大時，算法的執行時間T(n)和函數f(n)成正比。或者說，存在正常數c和n0，當n≥n0時，|T(n)|≤c|f(n)|。如果算法的執行時間T(n)與問題規模無關，是個常數，則記作T(n)=O(1)。在進行算法分析時，經常會用到如下三個定理：
定理一：若 T ( n ) = a m n m + a m − 1 n m − 1 + . . . + a 1 n + a 0 T(n)=a_{m}n^{m}+a_{m-1}n^{m-1}+...+a_{1}n+a_{0} T(n)=amnm+am−1nm−1+...+a1n+a0是一個m次多項式，則 T ( n ) = O ( n m ) T(n)=O(n^{m}) T(n)=O(nm)。
證明 取 n 0 = 1 ， 當 n ≥ n 0 時 n_{0}=1，當n≥n_{0}時 n0=1，當n≥n0時，有
∣ T ( n ) ∣ ≤ ∣ a m ∣ n m + ∣ a m − 1 ∣ n m − 1 + . . . + ∣ a 1 ∣ n + ∣ a 0 ∣ ≤ ( ∣ a m ∣ + ∣ a m − 1 ∣ + . . . + ∣ a 1 ∣ + ∣ a 0 ∣ ) n m |T(n)|≤|a_{m}|n^{m}+|a_{m-1}|n^{m-1}+...+|a_{1}|n+|a_{0}|≤(|a_{m}|+|a_{m-1}|+...+|a_{1}|+|a_{0}|)n^{m} ∣T(n)∣≤∣am∣nm+∣am−1∣nm−1+...+∣a1∣n+∣a0∣≤(∣am∣+∣am−1∣+...+∣a1∣+∣a0∣)nm
取 c = ∣ a m ∣ + ∣ a m − 1 ∣ + . . . + ∣ a 1 ∣ + ∣ a 0 ∣ c=|a_{m}|+|a_{m-1}|+...+|a_{1}|+|a_{0}| c=∣am∣+∣am−1∣+...+∣a1∣+∣a0∣，定理得證。
定理二：若 T 1 ( n ) 、 T 2 ( n ) T_{1}(n)、T_{2}(n) T1(n)、T2(n)分别是算法P1、P2的執行時間，并且
T 1 ( n ) = O ( f ( n ) ) T_{1}(n)=O(f(n)) T1(n)=O(f(n)) T 2 ( n ) = O ( g ( n ) ) T_{2}(n)=O(g(n)) T2(n)=O(g(n))
則依次執行算法P1和P2，總的執行時間
T ( n ) = O ( m a x ( ∣ f ( n ) ∣ , ∣ g ( n ) ∣ ) T(n)=O(max (|f(n)|,|g(n)|) T(n)=O(max(∣f(n)∣,∣g(n)∣)
證明 根據假設可知，存在正常數 c 1 c_{1} c1、 c 2 c_{2} c2、 n 1 n_{1} n1和 n 2 n_{2} n2，當n≥ n 1 n_{1} n1時，有 ∣ T 1 ( n ) ∣ ≤ c 1 ∣ f ( n ) ∣ |T_{1}(n)|≤c_{1}|f(n)| ∣T1(n)∣≤c1∣f(n)∣；當n≥ n 2 n_{2} n2時，有 ∣ T 2 ( n ) ∣ ≤ c 2 ∣ g ( n ) ∣ |T_{2}(n)|≤c_{2}|g(n)| ∣T2(n)∣≤c2∣g(n)∣。若依次執行算法算法P1和P2，則總的執行時間
∣ T ( n ) ∣ ≤ ∣ T 1 ( n ) ∣ + ∣ T 2 ( n ) ∣ ≤ c 1 ∣ f ( n ) ∣ + c 2 ∣ g ( n ) ∣ ≤ 2 m a x ( c 1 , c 2 ) m a x ( ∣ f ( n ) ∣ , ∣ g ( n ) ∣ ) |T(n)|≤|T_{1}(n)|+|T_{2}(n)|≤c_{1}|f(n)|+c_{2}|g(n)|≤2max(c_{1},c_{2})max (|f(n)|,|g(n)|) ∣T(n)∣≤∣T1(n)∣+∣T2(n)∣≤c1∣f(n)∣+c2∣g(n)∣≤2max(c1,c2)max(∣f(n)∣,∣g(n)∣)
取 c = 2 m a x ( c 1 , c 2 ) , n 0 = m a x ( n 1 , n 2 ) , c=2max(c_{1},c_{2}),n_{0}=max(n_{1},n_{2}), c=2max(c1,c2),n0=max(n1,n2),定理得證。
定理三：若 T 1 ( n ) 、 T 2 ( n ) T_{1}(n)、T_{2}(n) T1(n)、T2(n)分别是算法P1、P2的執行時間，并且
T 1 ( n ) = O ( f ( n ) ) T_{1}(n)=O(f(n)) T1(n)=O(f(n)) T 2 ( n ) = k ( n ) T 1 ( n ) T_{2}(n)=k(n)T_{1}(n) T2(n)=k(n)T1(n)則 T 2 ( n ) = O ( k ( n ) f ( n ) ) T_{2}(n)=O(k(n)f(n)) T2(n)=O(k(n)f(n))
證明 ∣ T 2 ( n ) ∣ = ∣ k ( n ) ∣ ∣ T 1 ( n ) ∣ ≤ ∣ k ( n ) ∣ ∣ c 1 ∣ ∣ f ( n ) ∣ = c 1 ∣ k ( n ) f ( n ) ∣ |T_{2}(n)|=|k(n)||T_{1}(n)|≤|k(n)||c_{1}||f(n)|=c_{1}|k(n)f(n)| ∣T2(n)∣=∣k(n)∣∣T1(n)∣≤∣k(n)∣∣c1∣∣f(n)∣=c1∣k(n)f(n)∣
取 c = c 1 , c=c_{1}, c=c1,定理得證。
用數量級形式 O ( f ( n ) O(f(n) O(f(n)表示算法執行時間 T ( n ) T(n) T(n)的時候，函數 f ( n ) f(n) f(n)通常取較簡單的形式，如1、log2n、n、nlog2n、n2、n3、2n等。在n較大的情況下，常見的時間複雜度之間存在如下關系：
O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n l o g 2 n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) O(1)<O(log_{2}n)<O(n)<O(nlog_{2}n)<O(n^{2})<O(n^{3})<O(2^{n}) O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)
3.1 算法分析舉例
例1 假設A[1]~A[n]中存放了n個整數，下面程式段的功能是确定其中值最大的整數在數組中的下标i。請分析程式段中每個語句的執行次數，并用數量級形式表示這個程式段的執行時間。
i=1; for(j=2;j<=n;j++) if(A[j]>A[i]) i=j;
解：第1行的指派語句執行1次；第2行的for語句執行n次；第3行的if語句執行n-1次；第4行的指派語句最多執行n-1次。由于程式段中語句總的執行次數是2n~3n-1次，是以，這個程式執行時間是O(n)。
例2 假設A[1]~A[n]中存放了n個整數，其中n>100。下面程式段的功能是求其中前100個整數的平均值。請分析程式段中每個語句的執行次數，并用數量級形式表示這個程式段的執行時間。
s=0.0; for(i=1;i<=100;i++) s=s+A[i]; cout<< s/100;
解：這個程式段共有4行，每一行語句分别執行了1次、101次、100次和1次。由于程式段中語句的執行次數和n無關，是以，這個程式段的執行時間是O(1)。
例3 下面程式段的功能是從n階整型矩陣中找出兩個值最小的整數，請分析其時間複雜度。
m1=32767; m2=m1; for(i=0; i< n; i++) for(j=0; j< n; j++) if(A[i] [j]< m1) {m2=m1;m1=A[i] [j];} else if(A[i] [j]< m2) m2=A[i] [j];
解：執行第1行指派語句所需時間是O(1)，執行一遍内循環體所需時間也是O(1)，由于内循環體總工執行了n2次，是以，程式段的執行時間為O(n2)。
例4 下面的程式段可用于求xn，請分析其時間複雜度。
y=1;u=x;v=n; while(v>0) { if(v%2 == 1) y=y*u; u=u*v;v=v/2; } cout<< y;
解：這個程式段的執行時間主要用在while循環上，循環次數和v的大小有關。由于v的初始值是n，每循環一遍，v的值被減半，是以，循環次數不超過 ⌊ l o g 2 n ⌋ \lfloor log_{2}n\rfloor ⌊log2n⌋ +1次（符号 ⌊ ⌋ \lfloor \rfloor ⌊⌋表示向下取整）。執行一遍循環體所需時間與n無關，是O(1)。是以，程式段的執行時間為
T ( n ) = ( ⌊ l o g 2 n ⌋ + 1 ) O ( 1 ) = O ( l o g 2 n ) T(n)=(\lfloor log_{2}n \rfloor +1)O(1)=O( log_{2}n) T(n)=(⌊log2n⌋+1)O(1)=O(log2n)
例5 下面的算法是用來求解著名的漢諾塔問題的，請分析算法的時間複雜度。
void hanoi(int n,char a,char b,char c) { if(n>0) { hanoi(n-1,a,c,b); cout<< a<<"->" << c; hanoi(n-1,b,a,c); } }
解：這是一個遞歸算法，器其執行時間T(n)與參數n有關。當n=0時，隻執行傳回操作，所需時間為T(n)=O(1)；當n>0時，執行了一個輸出語句，所需時間為O(1)，執行了兩個遞歸調用語句，所需時間為2T(n-1)。是以，算法的執行時間是
T ( n ) T(n) T(n) = 2 T ( n − 1 ) + 2 0 O ( 1 ) =2T(n-1)+2^{0}O(1) =2T(n−1)+20O(1)
= 2 2 T ( n − 2 ) + ( 2 1 + 2 0 ) O ( 1 ) =2^{2}T(n-2)+(2^{1}+2^{0})O(1) =22T(n−2)+(21+20)O(1)
= 2 3 T ( n − 3 ) + ( 2 2 + 2 1 + 2 0 ) O ( 1 ) =2^{3}T(n-3)+(2^{2}+2^{1}+2^{0})O(1) =23T(n−3)+(22+21+20)O(1)
. . . ... ...
= 2 n T ( 0 ) + ( 2 n − 1 + 2 n − 2 + . . . + 2 0 ) O ( 1 ) =2^{n}T(0)+(2^{n-1}+2^{n-2}+...+ 2^{0})O(1) =2nT(0)+(2n−1+2n−2+...+20)O(1)
= ( 2 n + 2 n − 1 + 2 n − 2 + . . . + 2 0 ) O ( 1 ) =(2^{n}+2^{n-1}+2^{n-2}+...+ 2^{0})O(1) =(2n+2n−1+2n−2+...+20)O(1)
= ( 2 n + 1 − 1 ) O ( 1 ) =(2^{n+1}-1)O(1) =(2n+1−1)O(1)
= O ( 2 n ) =O(2^{n}) =O(2n)