數(shù)據(jù)結構課件：第1章 緒論

1、1,數(shù)據(jù)結構,2,課程相關信息,教材：數(shù)據(jù)結構，劉大有等編著，高等教育出版社，2010年9月. 參考書目：清華大學出版社、高等教育出版社和機械出版社等出版的數(shù)據(jù)結構教材. 教學形式：理論實驗 考核方式：考試,3,參考書 1、數(shù)據(jù)結構 嚴蔚敏、吳偉民編著 清華大學出版社。 2、數(shù)據(jù)結構 （用面向?qū)ο蠓椒ㄅcC+描述） 殷人昆、陶永雷等編著 清華大學出版社,4,教學計劃,第一章 緒論(算法分析基礎) 第二章 線性表、堆棧、隊列 第三章 數(shù)組、字符串 第四章 樹 第五章 圖 第六章 遞歸 第七章 排序 第八章 查找,5,第一章 緒論,1.1 為什么要學習數(shù)據(jù)結構 1.2 數(shù)據(jù)結構概念 1.3 算法 1

2、.4 算法的正確性證明 1.5 算法分析基礎,6,1.1 為什么學習數(shù)據(jù)結構,計算機學科中一門重要的專業(yè)基礎課。 提高計算機的工作效率。 是程序設計的重要基礎； 是許多計算機專業(yè)課的基礎，如算法分析、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)等。,7,最短路徑算法在物流配送問題中的應用； 樹結構在數(shù)據(jù)挖掘領域中的應用； 散列技術在數(shù)據(jù)加密領域中的應用； 查找技術在數(shù)據(jù)庫領域中的應用； 倒排文件、查找算法在搜索引擎中的應用。,8,第一章 緒論,1.1 為什么要學習數(shù)據(jù)結構 1.2 數(shù)據(jù)結構概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎,9,例 個人書庫管理程序所要處理的數(shù)據(jù)可能是如下的表

3、格。,10,1.2 數(shù)據(jù)結構概念1. 數(shù)據(jù),數(shù)據(jù)是對象的表示。 計算機程序要處理的“原料”，它可以被計算機識別、存儲和加工處理。 包括：數(shù)值、文字、表格、圖像、聲音、源程序等。,11,數(shù)據(jù)元素,是組成數(shù)據(jù)的基本單位。 在程序中通常把一個數(shù)據(jù)元素作為一個整體來考慮和處理。 數(shù)據(jù)元素還可被稱為結點或頂點。 例如，在上表中，把其中的每一行（代表一本書）作為一個基本單位來考慮。,12,數(shù)據(jù)項,一個數(shù)據(jù)元素含有若干個數(shù)據(jù)項。 例如，在上表數(shù)據(jù)中，每個數(shù)據(jù)元素由登錄號、書號、書名、作者、出版社和價格六個數(shù)據(jù)項構成。 數(shù)據(jù)項是構成數(shù)據(jù)的最小單位。,13,例 電話號碼薄的查詢問題。 (a1，b1 ), (a2

4、，b2), (an，bn ),14,例2 學生自然情 況查詢問題。,15,2. 邏輯結構,數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素及其間的邏輯關系。 在個人書庫管理程序中，各數(shù)據(jù)元素之間在邏輯上有一種線性關系，它指出了10個數(shù)據(jù)元素在表中的排列順序。,16,有些書也將數(shù)據(jù)的邏輯結構分為集合、線性結構、樹和圖等四種類型。其中，集合的特點是：結構中的數(shù)據(jù)元素之間除了同屬于一個集合的關系外，別無其他關系。,集合,線性結構,樹,圖,17,邏輯結構的形式化表示,邏輯結構表示為二元組L=(N, R)， N是結點的有限集合 R是N上的關系集合,18,例 L=(N,R)， N=a, b, c, d, e , R=r， r=

5、, , , ,若a，bN，且關系r，則稱a是b的前趨結點，稱b是a的后繼結點，稱a和b是相鄰結點； 如果不存在aN，使r ，則稱b為始結點； 如果不存在bN ，使r，則稱a為終結點； 既非始結點又非終結點的結點被稱為內(nèi)結點。,19,例 L=(N,R)， N=k1,k2,k9, R=r，r=, , , , , , , ,20,邏輯結構的分類 線性結構 結構中有且僅有一個始結點和一個終結點，始結點只有一個后繼結點，終結點只有一個前趨結點，每個內(nèi)結點有且僅有一個前趨結點和一個后繼結點。 非線性結構（樹、圖） 結構中的結點可能有多個前趨結點和多個后繼結點。,21,3存儲結構 數(shù)據(jù)的存儲結構是指數(shù)據(jù)的邏

6、輯結構在計算機中所需的存儲空間、空間的構成結構及對該存儲結構的訪問方式等的總稱。 數(shù)據(jù)的存儲結構是建立一種由邏輯結構到存儲空間的映射。 個人書庫數(shù)據(jù)，在計算機中可以有多種存儲表示。如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。,22,存儲結構分類,1）順序存儲結構 把一組結點存放在地址相鄰的存儲單元里，結點間的邏輯關系用存儲單元的自然順序關系表達。,23,23,2）鏈接存儲結構 在結點的存儲結構中附加指針字段，兩個結點的邏輯后繼關系用指針的指向來表達。,(a)可用存儲空間,24,存儲結構分類,3）索引存儲結構 索引表把整數(shù)索引值映射到結點的存儲地址。 索引表存儲一串指

7、針，每個指針指向存儲區(qū)域的一個數(shù)據(jù)結點。,25,存儲結構分類,4）散列存儲結構 適用于大數(shù)據(jù)量、高速檢索的場合。 索引存儲的一種延伸和擴展，利用散列函數(shù)進行索引值的計算，并通過索引表求出結點的指針地址。,26,存儲結構總結,順序、鏈接、索引和散列存儲結構，可以單獨使用，也可以組合使用。 存儲結構要正確反映邏輯結構，并便于操作。,27,4. 對數(shù)據(jù)的操作,插入 刪除 修改 排序 查找,28,數(shù)據(jù)結構的定義： 數(shù)據(jù)結構就是研究數(shù)據(jù)的邏輯結構和物理結構以及他們之間的關系，并對這種結構定義相適應的運算，設計出相應的算法。,5.數(shù)據(jù)結構的概念,29,數(shù)據(jù)結構的概念,按某種邏輯關系將一批數(shù)據(jù)元素組織起來；

8、 按一定的存儲方式把它們存儲起來； 在數(shù)據(jù)上定義需要施加的操作。,30,數(shù)據(jù)結構課程的目的,從對問題抽象和求解的角度來學習常用的數(shù)據(jù)結構，闡明其內(nèi)在的邏輯關系和在計算機中的存儲表示，以及刻畫施加于其上之各種操作的算法。 學習上述理論知識，綜合運用相關知識，再結合上機實踐，使我們具備求解比較復雜的問題的能力，即掌握問題求解建模，選擇恰當數(shù)據(jù)結構，或構造新的數(shù)據(jù)結構，設計較優(yōu)算法，證明算法（或算法之關鍵步驟）正確性，分析算法的時空復雜性，對算法編程、調(diào)試等能力。,31,數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的集合的總稱。 抽象數(shù)據(jù)類型：由一組數(shù)據(jù)結構和在該組數(shù)據(jù)結構上的一組操作所組成

9、。,32,第一章 緒論,1.1 為什么要學習數(shù)據(jù)結構 1.2 數(shù)據(jù)結構的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎,33,計算機解決問題的步驟： 從具體問題中抽象出一個適當?shù)臄?shù)學模型； 設計解此模型的方法； 編出程序、進行測試、調(diào)試，直至得到最終解答。 計算機處理問題，以適當?shù)臄?shù)據(jù)結構為基礎，制定出的切實可行的方法和步驟計算機算法。,1.3 算法1.算法的概念,34,計算機算法與數(shù)據(jù)結構密切相關:算法無不依附于具體的數(shù)據(jù)結構，數(shù)據(jù)結構直接關系到算法的選擇和效率。 對數(shù)據(jù)的操作是由計算機來完成，這就要設計相應的插入、刪除和修改等算法 。 1976年，沃斯提出：算法+數(shù)據(jù)結

10、構=程序,算法與數(shù)據(jù)結構的關系,35,算法由有限條指令構成，規(guī)定了解決特定問題的一系列操作。 算法具有5個特性： (1)有限性：一個算法在執(zhí)行有限步后必然終止。 (2)確定性：算法中的每條指令都必須是清楚的，指令無二義性，相同的輸入必須有相同的輸出。 (3)輸入：具有0個或0個以上由外界提供的量。 (4)輸出：產(chǎn)生1個或多個結果。 (5)可行性：每條指令都十分基本，原則上可由人僅用筆和紙在有限的時間內(nèi)也能完成。 算法與程序的區(qū)別 表現(xiàn)形式不同。 是否具備有窮性。,36,算法可以用自然語言、數(shù)學語言、程序設計語言或約定的任何符號語言來描述。如類Pascal語言、C語言或偽代碼等。 ADL語言直觀

11、方便。,2.算法描述語言ADL,37,算法描述語言ADL的格式 算法(變量i1,變量im.變量j1,變量jn)/單行注釋（或/*/多行注釋） . 本步驟的概括說明 . 本步驟的概括說明 語句序列. ,38, 表達式 算術運算符 +,-,*,/,DIV,MOD, , 關系運算符= 、 、 邏輯運算符AND，OR，NOT 邏輯常量 true，false 集合運算符 ，（差）， 語句 每條語句都用“.”作為結束符 賦值語句 a b. a b. a b c.,39, 條件語句 1) IF THEN (語句1. . 語句m ). 2) IF THEN (語句1. . 語句m ). ELSE (語句1.

12、. 語句n ). 3) CASE DO ( : (語句1. .語句n1). : 語句1. .語句nm).,40,循環(huán)語句 1) WHILE DO (語句1. . 語句n ). 2) FOR = TO STEP DO (語句1. . 語句n ). 3) FOR DO (語句1. . 語句n ).,41,轉(zhuǎn)移語句 GOTO () . EXIT 語句 結束本層WHILE或者FOR循環(huán)的執(zhí)行 RETURN 語句 指出算法執(zhí)行的終點 其它 輸入語句：READ(x) /讀取輸入值賦給變量x 輸出語句：PRINT(),42,例 A是一個含有n個不同元素的實數(shù)數(shù)組，給出求A之最大和最小元素的算法。 算法SM(

13、A, n . max,min) SM1. 初始化 maxminA1. SM2. 比較 FOR I=2 TO n DO /求最大和最小元素 ( IF AI max THEN maxAI. IF AI min THEN minAI) . ,43,ADL 的特點,書寫簡便 不必考慮過多程序設計語言的細節(jié) 例：交換a和b的值 易于理解 不同編程習慣的人交流算法 不必考慮與算法無關的內(nèi)容（開發(fā)及運行環(huán)境、編譯狀態(tài)）,44,3. 算法的評價準則 評估算法性能的5條準則 正確性 時間復雜性 占用空間 可讀性 魯棒性,45,1)正確性 說一個算法是正確的，如果對于一切合法的輸入數(shù)據(jù)，該算法執(zhí)行有限時間都能產(chǎn)生

14、正確的結果。 具體包括兩方面：一是解決問題的方法；二是實現(xiàn)這一方法的一系列指令(步驟、語句)。 證明相關的引理和定理，以確認一個算法所用方法的正確性； 證明一系列語句確實做了符合規(guī)定的操作.,46,語句正確性，大體可分為四個層次： 算法不含語法錯誤； 算法對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； 算法對于精心選擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)，能夠得出滿足要求的結果； 算法對一切合法的輸入數(shù)據(jù)，都能產(chǎn)生滿足要求的結果。,47,2) 時間復雜性 算法的實際執(zhí)行時間是不是時間復雜性的理想度量呢? 不是。 其原因是： 算法的實際執(zhí)行時間依賴于機器。同一個算法在不同機器上的執(zhí)行時間不一定相同。 算

15、法的實際執(zhí)行時間還依賴于編寫算法的程序設計語言。一個用 C 或 Pascal 編寫的算法可能要比用 BASIC 語言編寫的算法快 20 倍。,48,3) 占用的存儲空間 包括存儲算法本身所占用的存儲空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲空間和算法運行過程中臨時占用的存儲空間。 算法在運行過程中所占用的存儲空間的大小被定義為算法的空間復雜性。它包括局部變量所占用的存儲空間和系統(tǒng)為了實現(xiàn)遞歸所使用的堆棧這兩個部分。算法的空間復雜性一般以數(shù)量級的形式給出。,49,4) 可讀性 最簡單、最直接的算法盡管不一定是最有效的，但卻具有良好的可讀性?？勺x性好的算法其正確性證明比較容易（即其正確性易于保證），同

16、時便于設計、修改、閱讀和調(diào)試，可見可讀性是十分重要的。 對于那些需經(jīng)常使用的算法來說，高效率比可讀性更為重要。,50,5) 魯棒性 對有缺失、有噪聲或有錯誤的輸入數(shù)據(jù)，算法應具有較強的應付能力。如，能對輸入數(shù)據(jù)語法語義檢驗、提出修改錯誤的建議并提供重新輸入的機會。,51,1.4 算法的正確性證明,對于一個算法來說正確性是前提，也是最重要的。 對明顯是正確的算法，可通過上機調(diào)試驗證其正確性。調(diào)試用的數(shù)據(jù)要精心挑選，以保證算法對“所有的”數(shù)據(jù)都是正確的; 只要調(diào)試找出一組數(shù)據(jù)使算法失敗(即計算結果不正確)，就能否定整個算法的正確性; 算法的正確性一般通過數(shù)學方法進行推理證明，常用的數(shù)學方法除了直接

17、證明法外，還有反證法和數(shù)學歸納法。,52,第一章 緒論,1.1 為什么要學習數(shù)據(jù)結構 1.2 數(shù)據(jù)結構的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎,53,Testing (測試),Black Box Methods 黑盒法 側(cè)重測試程序的功能，不考慮程序是如何實現(xiàn)的，即代碼結構。 設計測試用例，檢查能否得到預想的結果。 White Box Methods 白盒法 側(cè)重測試程序的代碼結構 Statement Coverage 語句覆蓋: 使程序中的每一條語句都至少執(zhí)行一次。 Decision Coverage 分支覆蓋 ：使程序中的每一個分枝都至少執(zhí)行一次。,54,1.

18、反證法,1)要證明定理 T 是正確的，首先假定 T是錯誤的 2)使用正確的命題和正確的推理規(guī)則進行推理, 若出現(xiàn)下列條件之一，就會得出矛盾的結果： 與已知條件矛盾 與公理矛盾 與證明過的定理矛盾 自相矛盾 3)由此推出定理 T 是正確的。,55,例 證明沒有最大的整數(shù),證明：用反證法。 (1) 反面假設：假設存在一個最大整數(shù)，記為N . (2) 由假設推出矛盾：設P N 1，因為P 是兩個整數(shù)的和，所以P也是整數(shù)，且 P N . 與 N 是最大整數(shù)矛盾。 (3) 肯定原來的結論：因此，沒有最大的整數(shù)。證畢。,56,2. 數(shù)學歸納法,數(shù)學上證明與自然數(shù) N 有關的命題的一種特殊方法，它主要用來研

19、究與正整數(shù)有關的數(shù)學問題。 數(shù)學歸納法依靠假設的事實來證明定理，是用“有限”步驟解決“無限”問題的一種嚴格證明方法。,57,數(shù)學歸納法： 設T是一個定理， n是T中的正參數(shù). 數(shù)學歸納法表明，如果下面兩個條件為真，則對于參數(shù)n的任何值，T都是正確的： (1) 基礎歸納：n c 時，T成立。 (2) 歸納步驟：如果n = k 1 時T 成立，則n = k 時T也成立。 其中，c是一個較小的常量，n c . 通常，證明初始歸納很容易，而證明歸納步驟很難。,58,強歸納法 設T是一個定理， n是T中的正參數(shù). 數(shù)學歸納法表明，如果下面兩個條件為真，則對于參數(shù)n的任何值，T都是正確的： (1) 基礎歸

20、納：n c 時，T成立。 (2) 歸納步驟：如果n = k 1 時T 成立，則n = k 時T也成立 (2) 歸納步驟：如果對于所有的k ( c k n ) T 都成立，則T 對于 n 也成立。,59,例: 證明由遞歸關系式T ( n ) T ( n 1 ) 1，T(1) 0，可推出T(n)n 1，其中，n 1 . 證明： 基礎歸納：n 1 時，T ( 1 ) 1 1 0，結論成立。 歸納步驟： 假設 T ( n 1 ) n 2 成立（歸納假設） 往證 T ( n ) n 1 成立。 由遞歸關系式可知： n 1 時，有T ( n ) T ( n 1 ) 1 再由歸納假設： T ( n ) T

21、( n 1 ) 1 n 2 1 n 1 由數(shù)學歸納法推出T (n) n 1成立，證畢,60,第一章 緒論,1.1 為什么要學習數(shù)據(jù)結構 1.2 數(shù)據(jù)結構的概念 1.3 算法 1.4 算法的正確性證明 1.5 算法分析基礎,61,1.5 算法分析基礎 在假定算法正確的前提下，用時間復雜性作為評價算法優(yōu)劣的標準。 一個算法的時間復雜性是指該算法所執(zhí)行的基本運算的次數(shù)。 最優(yōu)算法的定義： 某算法A為最優(yōu)，當且僅當解決同一領域同一問題的所有算法集合SA (ASA)中沒有一個算法執(zhí)行的基本運算次數(shù)比算法A更少。,62, 決定運行時間的因素： 、問題的規(guī)模。 、對源程序進行編譯所需時間。 、機器執(zhí)行指令的

22、速度。 、程序中指令重復執(zhí)行的次數(shù)。 頻度：算法執(zhí)行一次，某一語句實際被執(zhí)行的 次數(shù)，叫該語句在此算法中的頻度。,63,1.算法時間復雜性的分析方法 例 A是一個含有n個不同元素的實數(shù)數(shù)組，給出求A之最大和最小元素的算法。 算法SM (A,n . max,min) SM1初始化 maxminA1. SM2比較 FOR i=2 TO n DO ( IF Ai max THEN maxAi. IF Ai min THEN minAi). 算法SM的時間復雜性為2(n-1)。,64,例 實數(shù)數(shù)組R由n個元素組成，給定一個實數(shù)K，試確定K是否是R的元素。 算法F (R, n, K. i) F1 初始化

23、 i 1. F2 比較 WHILE in DO ( IF Ri=K THEN RETURN. i i+1) . 最少比較次數(shù)：1 最大比較次數(shù)：n,65,定義 設一個領域問題的輸入規(guī)模為n，Dn是該領域問題的所有輸入的集合，任一輸入IDn，P(I)是I出現(xiàn)的概率，且滿足 P(I)=1，T(I)是算法在輸入I下所執(zhí)行的基本運算次數(shù)。我們定義該算法的期望復雜性（即該算法的平均復雜性 ）為： E(n)= P(I)*T(I) 該算法的最壞復雜性為： W(n)=maxT(I) 該算法的最好復雜性為： W(n)=minT(I),66,R1 R2 R3 R4 R5 R6 R7 R8 5 20 12 7 30

24、 40 25 16,K=Ri q/n,K!=Ri 1-q,上例中，設q( 0q1 )為K 在R中的概率,q,67,通過計算我們可以得到算法F的期望復雜性為 E(n)= P(I)*T(I) =(q/n)*1+ (q/n)*2+ (q/n)*n+(1-q)*n n項 1項 = q(n+1)/2+(1-q)n 如果已知K在R中，即q=1，則有 E(n)= (n+1) /2 由算法F很容易看出該算法的最壞復雜性為 W(n)=maxT(i)| 1i n+1=n,68,例 算法 SM 的改進算法 BS 算法BS（A , i , j . fmax , fmin） /* 在數(shù)組 A 的第 i 至第 j 個元素

25、間尋找最大和最小 元素，已知 i j; 假定A 中元素互異 */ BS1. 遞歸出口 IF i j THEN (fmax fmin Ai. RETURN.) IF i j 1 THEN (IF Ai Aj THEN(fmax Aj. fmin Ai). ELSE (fmax Ai. fmin Aj). RETURN). BS2. 取中值 mid (ij)/2 BS3. 遞歸調(diào)用 BS (A, i, mid. Gmax, gmin). BS (A, mid1, j. hmax, hmin). BS4. 合并 fmax maxgmax, hmax. fmin mingmin, hmin. ,69,

26、i=1 mid= 4 j=8 A1 A2 A3 A4 A5 A6 A7 A8 5 20 12 7 30 40 25 16,算法SM的改進,70,BS(A , i1 , j8 . fmax , fmin) BS1. BS2. mid4 . BS3. BS(A , i1 , j4. gmax , gmin) BS1. BS2. mid2 . BS3. BS(A , i1 , j2. gmax , gmin) BS1. gmax20. gmin5 . RETURN. BS(A , i3 , j4. hmax , hmin) BS1. hmax12. hmin7. RETURN. BS4. gmax2

27、0 . gmin5 . BS(A , i5 , j8. hmax , hmin) BS1. BS2. mid6 . BS3. BS(A , i5 , j6. gmax , gmin) BS1. gmax40. gmin30. RETURN. BS(A , i7 , j8. hmax , hmin) BS1. hmax25. hmin16. RETURN. BS4. hmax40 . hmin16 . BS4. fmax 40 . fmin 5 . ,71,容易看出，BS對Ai到Aj的不同的輸入都有相同的基本運算次數(shù)。設T(n)表示其基本運算次數(shù)，則根據(jù)算法BS的遞歸過程，有如下的遞歸表達式：,

28、若 n 是 2 的冪(即存在正整數(shù)k , 使得 n2k )則有 T(n)2T(n/2)22(2T(n/4)2)2 4T(n/4)424(2T(n/8)2)42 8T(n/8)842 2k1T(2)(21222k1)(3n/2)2,72,BS與SM的比較 算法SM和BS的時間復雜性均為線性，但因3n/222(n1)，故算法BS優(yōu)于算法SM. 算法BS是遞歸算法，因此它的實現(xiàn)需要額外的輔助空間棧。,73,例 求下列各程序段時間復雜性。 for(i=1;i=n;i+) x+; for(j=1;j=n;j+) for(k=1;k=n;k+) x+; 計算時間復雜度 算法的計算時間個語句頻度 記做 T(

29、n),74,算法運行時間復雜度：指某算法的基本操作次數(shù)。 基本操作次數(shù)：最里層循環(huán)體內(nèi)簡單操作的執(zhí)行次數(shù)或遞歸調(diào)用的調(diào)用次數(shù)。 例3 for(i=1;i=n;i+) for(j=1;j=n;j+) x+;,75,確定算法基本運算次數(shù)的目的在于能比較功能相同的兩個算法之間的時間復雜性；預測隨實例特性的改變，運行時間的增減情況。 在很多情況下，特別當輸入規(guī)模 n 較大時，確定一個算法的基本運算次數(shù)T，得到T 和 n 之間的函數(shù)關系非常困難。 算法分析中通常采用大O、大和大來漸近表示算法的基本運算次數(shù)。,2. 復雜性函數(shù)的漸近表示,76,1892年，保羅巴赫曼(Paul Bachmann)提出了大O

30、表示法，主要用于估計函數(shù)的增長速率。 定義 設f(n)和g(n)是正整數(shù)集到正實數(shù)集上的函數(shù)，稱f(n)是O(g(n)，當且僅當存在正的常數(shù)C 和 n0，使得對任意的n n0 ，有 f(n) Cg(n) . f 和 g 之間關系的含義是“f(n)的階至多為g(n)”或“f 至多與g 增長得一樣快” .,大O表示法,77,例 f (n) 3 n 2 是 O(n) . 證明： 由大O的定義，存在C 3，n0 1，使得對任意的 n n0 ，有3 n 2 3 n 即 f(n) Cg(n) . 例 f (n) 3 log n loglog n 是 O (logn)證明：由大O的定義，存在C 4， n0 2，使得對任意的 n n0 ，有3 log n loglog n 4 logn 即 f(n) Cg(n) .,78,一個算法的時間復雜性為 O(g(n)，表明它的基本運算次數(shù)至多是 g(n) 的某個常數(shù)倍. O(1) 表示算法的時間復雜性為一常數(shù). O(n)、O(n2)、O(n3)、O(nm) 和 O(2n) 分別表示算法時間復雜性為線性階的、平方階的、立方階的、多項式階的和指數(shù)階的，其中