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

數(shù)據(jù)結構

——C++語言描述1為什么要學習數(shù)據(jù)結構這門課程當今科學研究的三大手段：理論實驗計算“計算”是隨著計算技術的發(fā)展而出現(xiàn)的新型手段。

如用計算機進行模擬實驗，而后確定方案——計算模擬是“計算”的特長之一：在制造某半導體時，用計算機模擬各種配方所得材料的特性，確定配方后再實際試驗制造生物制藥公司也是用計算模擬確定配方后再做實驗驗證(生化試劑昂貴啊)汽車碰撞也是先計算模擬碰撞，確定設計，再用車做碰撞實驗核武器設計也采用計算模擬核武器爆炸可是，為什么要學習數(shù)據(jù)結構？為什么要學習數(shù)據(jù)結構這門課程現(xiàn)代社會計算和計算機無處不在：手機上網(wǎng)微信、QQ微博游戲、電影、動畫各種智能家電：電視機似乎我們離不開計算機了可是，為什么要學習數(shù)據(jù)結構？3數(shù)據(jù)結構是一門什么課程數(shù)據(jù)結構是一門講述如何在計算機中存儲數(shù)據(jù)和處理數(shù)據(jù)的課程通俗的說，數(shù)據(jù)結構還是一門學習寫程序的課——更高級的程序設計課程學編程的境界學會寫程序學會高效地寫程序學會寫高效的程序學會設計算法學會設計有用的算法

本院各專業(yè)都與“計算”相關直接相關：信息與計算科學間接相關：數(shù)學與應用數(shù)學概率、統(tǒng)計學無論哪個專業(yè)，當需要使用計算機解決問題時，就會用到數(shù)據(jù)結構與算法6課程性質數(shù)據(jù)結構是計算科學學科及其相關學科的基礎課

公共基礎課、專業(yè)基礎課、專業(yè)方向課、專業(yè)選修課在教學計劃中的地位：核心、承上啟下

前導課：高等數(shù)學、離散數(shù)學、程序設計語言后續(xù)課：算法設計、數(shù)據(jù)庫、操作系統(tǒng)、計算機網(wǎng)絡、編譯原理……屬于武術中的“練功”科目

“練武不練功，到頭一場空”考研：專業(yè)課必考（初試或復試）教學目標掌握基本的數(shù)據(jù)結構

工具箱→復用、修改、重組培養(yǎng)算法設計能力、程序設計能力

算法——程序的靈魂問題求解過程：問題→想法→算法→程序程序設計研究的層次：算法→方法學→語言→工具培養(yǎng)算法分析能力

評價算法、改進算法學習要求循序漸進，切忌心浮氣躁提高課外學習的時間和內容理解科學而不是背誦科學→讀書正確對待考試做習題

華羅庚：“學數(shù)學不做習題等于入寶山而空返”

做實驗

計算機學科是一門科學性與工程性并重的學科，表現(xiàn)為理論和實踐緊密結合的特征。

學習要求循序漸進，切忌心浮氣躁提高課外學習的時間和內容理解科學而不是背誦科學→讀書正確對待考試作習題

有人說：“學數(shù)據(jù)結構不做習題和實驗等于入寶山而空返”

作實驗

計算機學科是一門科學性與工程性并重的學科，

表現(xiàn)為理論和實踐緊密結合的特征。

主教材

王紅梅,胡明,王濤.數(shù)據(jù)結構（C++版）第2版.清華大學出版社

輔導及實驗教材

王紅梅等.數(shù)據(jù)結構（C++版）學習輔導與實驗指導（第2版）.

清華大學出版社

參考教材

1.嚴蔚敏.數(shù)據(jù)結構.清華大學出版社.1997

2.張銘.數(shù)據(jù)結構與算法.高等教育出版社.2008

3.曹宏慶譯.如何求解問題.中國水利水電出版社.2003關于教材關于C++參考書林瑤等譯，《

C++大學自學教程(第7版)》，AlStevens,Dr.Dobb‘sJournal

，電子工業(yè)出版社，2004年1月裘宗燕譯，《C++程序設計語言（特別版）》，BjarneStroustrup（C++語言的作者）,機械工業(yè)出版社，2002-7-1

潘愛民等譯，《C++Primer(3RD)中文版》，StanleyB.Lippman,JoseeLajoie，中國電力出版社,

2002-4-1

周靖等譯，《C++編程金典（第3版）》，H.M.Deitel,P.J.Deitel，清華大學出版社，2002-9-1劉宗田等譯，《C++編程思想》，BruceEckel，機械工業(yè)出版社，2000-1-1成績組成理論課成績平時成績

10％~20%：出勤＋作業(yè)＋實驗期中考試成績

40％~50%期末考試成績

40％~50%實驗課成績：出勤＋實驗＋期末成績：百分制有關通過網(wǎng)絡交作業(yè)和實驗的要求將作業(yè)或實驗相關文件壓縮打包上傳，具體要求如下：壓縮包文件命名格式：

<學號><姓名><作業(yè)或實驗說明>

如：00281001王五實驗2

00281001王五第一章作業(yè)不同的實驗和作業(yè)用不同的壓縮包文件上傳，不要合在一個壓縮包文件中；對實驗壓縮包，要求將該次實驗工程所在目錄中的所有文件（要包括目錄,但要刪除其中的debug目錄）壓縮，并按如上命名：

00281001王五實驗2.rar將壓縮文件上傳到指定的目錄即可；實驗提交和作業(yè)提交地址：6/

提交時用戶名：student密碼：123456

實驗課要求到實驗室上機課件下載地址：

6/

用戶名：zsuzyd密碼：123456

下載請用FTP軟件FileZillaQQ:413393491，E-Mail:用qq郵箱（通常處于潛水狀態(tài)，有問題請留言。）第1章緒論數(shù)據(jù)結構在程序設計中的作用本課程討論的主要內容數(shù)據(jù)結構的基本概念算法及算法分析本章的基本內容是：1938年出生，25歲畢業(yè)于加州理工學院數(shù)學系，博士畢業(yè)后留校任教，28歲任副教授。30歲時，加盟斯坦福大學計算機系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming，他計劃共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計算機科學界的最高榮譽——圖靈獎，此時，他年僅36歲。數(shù)據(jù)結構的創(chuàng)始人——克努思1.1數(shù)據(jù)結構在程序設計中的作用程序設計的實質是什么?數(shù)據(jù)表示：將數(shù)據(jù)存儲在計算機（內存）中數(shù)據(jù)處理：處理數(shù)據(jù)，設計方案（算法）數(shù)據(jù)結構問題起源于程序設計

1.1數(shù)據(jù)結構在程序設計中的作用利用計算機求解問題的一般過程?計算機不能分析問題并產生問題的解決方案，必須由人來分析問題，確定問題的解決方案，編寫程序，然后讓計算機執(zhí)行程序最終獲得問題的解。1.1數(shù)據(jù)結構在程序設計中的作用例1-1手機電話號碼查詢問題將電話號碼集合組織成線性結構和樹結構，查找操作的效率不同，當數(shù)據(jù)量較大時差別就更大。1.2本課程討論的主要內容計算機求解問題:

問題→抽象出問題的模型→求模型的解問題——數(shù)值問題、非數(shù)值問題數(shù)值問題→數(shù)學方程非數(shù)值問題→數(shù)據(jù)結構例1-2學籍管理問題完成什么功能?各表項之間是什么關系？1.2本課程討論的主要內容例1-3人——機對弈問題如何實現(xiàn)對弈?各格局之間是什么關系？1.2本課程討論的主要內容例1-4七巧板涂色問題

如何表示區(qū)域之間的鄰接關系？1.2本課程討論的主要內容本課程討論非數(shù)值問題的數(shù)據(jù)組織和處理，主要內容如下：（1）數(shù)據(jù)的邏輯結構：線性表、樹、圖等數(shù)據(jù)結構，其核心是如何組織待處理的數(shù)據(jù)以及數(shù)據(jù)之間的關系；（2）數(shù)據(jù)的存儲結構：如何將線性表、樹、圖等數(shù)據(jù)結構存儲到計算機的存儲器中，其核心是如何有效地存儲數(shù)據(jù)以及數(shù)據(jù)之間的邏輯關系；（3）算法：如何基于數(shù)據(jù)的某種存儲結構實現(xiàn)插入、刪除、查找等基本操作，其核心是如何有效地處理數(shù)據(jù)；（4）常用數(shù)據(jù)處理技術：查找技術、排序技術、索引技術等。1.2本課程討論的主要內容1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)：所有能輸入到計算機中并能被計算機程序識別和處理的符號集合。數(shù)值數(shù)據(jù)：整數(shù)、實數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)項：構成數(shù)據(jù)元素的不可分割的最小單位。數(shù)據(jù)結構的基本概念學號姓名性別出生日期政治面貌0001陸宇男1986/09/02團員0002李明男1985/12/25黨員0003湯曉影女1986/03/26團員數(shù)據(jù)項數(shù)據(jù)元素數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項之間的關系包含關系：數(shù)據(jù)由數(shù)據(jù)元素組成，數(shù)據(jù)元素由數(shù)據(jù)項組成。數(shù)據(jù)元素是討論數(shù)據(jù)結構時涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項一般不予考慮。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構數(shù)據(jù)元素關系數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念關聯(lián)方式或鄰接關系數(shù)據(jù)的邏輯結構是從具體問題抽象出來的數(shù)據(jù)模型學籍管理問題中，表項之間的邏輯關系指的是什么？人機對弈問題中，格局之間的邏輯關系指的是什么？教學計劃編排問題中，課程之間的邏輯關系指的是什么？數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念數(shù)據(jù)的邏輯結構在形式上可定義為一個二元組：Data_Structure=(D,R)其中D是數(shù)據(jù)元素的有限集合，R是D上關系的集合。數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念Data_Structure=(D,R)其中D={A,B,C,D,E,F,G}R={R1}，R1={<A,B>,<A,E>,<A,F>,<B,C>,<B,D>,<C,D>,<D,E>,<D,G>,<E,F>,<E,G>}數(shù)據(jù)結構：相互之間存在一定關系的數(shù)據(jù)元素的集合。按照視點的不同，數(shù)據(jù)結構分為邏輯結構和存儲結構。邏輯結構：指數(shù)據(jù)元素之間邏輯關系的整體。存儲結構：又稱為物理結構，是數(shù)據(jù)及其邏輯結構在計算機中的表示。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念內存存儲結構實質上是內存分配，在具體實現(xiàn)時依賴于計算機語言。數(shù)據(jù)結構從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念數(shù)據(jù)結構從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；⑵線性結構：數(shù)據(jù)元素之間存在著一對一的線性關系；1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念數(shù)據(jù)結構從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；⑵線性結構：數(shù)據(jù)元素之間存在著一對一的線性關系；⑶樹結構：數(shù)據(jù)元素之間存在著一對多的層次關系；1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念數(shù)據(jù)結構從邏輯上分為四類：⑴集合：數(shù)據(jù)元素之間就是“屬于同一個集合”；⑵線性結構：數(shù)據(jù)元素之間存在著一對一的線性關系；⑶樹結構：數(shù)據(jù)元素之間存在著一對多的層次關系；⑷圖結構：數(shù)據(jù)元素之間存在著多對多的任意關系。1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念通常有兩種存儲結構：1.順序存儲結構：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系由元素的存儲位置來表示?！璪atcateat…起始地址例：（bat,cat,eat）1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念通常有兩種存儲結構：1.順序存儲結構：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系由元素的存儲位置來表示。2.鏈接存儲結構：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關系用指針來表示。例：（bat,cat,eat）1.3數(shù)據(jù)結構的基本概念數(shù)據(jù)結構的基本概念0200020803000325…………bat0200cat0325eat∧邏輯結構和存儲結構之間的關系數(shù)據(jù)的邏輯結構屬于用戶視圖，是面向問題的，反映了數(shù)據(jù)內部的構成方式；數(shù)據(jù)的存儲結構屬于具體實現(xiàn)的視圖，是面向計算機的。一種數(shù)據(jù)的邏輯結構可以用多種存儲結構來存儲，而采用不同的存儲結構，其數(shù)據(jù)處理的效率往往是不同的。

1.3數(shù)據(jù)結構的基本概念抽象數(shù)據(jù)類型1.數(shù)據(jù)類型（DataType）：一組值的集合以及定義于這個值集上的一組操作的總稱。

例如：C++中的整型變量

2.抽象（Abstract）:抽出問題本質的特征而忽略非本質的細節(jié)。

例如：地圖、駕駛汽車3.抽象數(shù)據(jù)類型（AbstractDataType，ADT）:一個數(shù)據(jù)結構以及定義在該結構上的一組操作的總稱。1.3數(shù)據(jù)結構的基本概念1.3數(shù)據(jù)結構的基本概念抽象數(shù)據(jù)類型在設計ADT時，把ADT的定義、設計和實現(xiàn)分開來。定義部分只包含數(shù)據(jù)的邏輯結構和所允許的操作集合，一方面，ADT的使用者依據(jù)這些定義來使用ADT，即通過操作集合對該ADT進行操作；另一方面，ADT的實現(xiàn)者依據(jù)這些定義來完成該ADT各種操作的具體實現(xiàn)。ADT抽象數(shù)據(jù)類型名Data數(shù)據(jù)元素之間邏輯關系的定義Operation

操作1

前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài)

輸入：執(zhí)行此操作所需要的輸入

功能：該操作將完成的功能

輸出：執(zhí)行該操作后產生的輸出

后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài)操作2

…………操作n……endADT

1.3數(shù)據(jù)結構的基本概念抽象數(shù)據(jù)類型1.3數(shù)據(jù)結構的基本概念（小結）數(shù)據(jù)的操作：插入、刪除、修改、檢索、排序等數(shù)據(jù)的邏輯結構數(shù)據(jù)的存儲結構順序存儲鏈式存儲集合線性結構樹結構圖結構非數(shù)值問題數(shù)據(jù)表示算法的相關概念1.算法（Algorithm）:是對特定問題求解步驟的一種描述，是指令的有限序列。2.

算法的五大特性：⑴

輸入：一個算法有零個或多個輸入。⑵輸出：一個算法有一個或多個輸出。⑶有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。⑷確定性：算法中的每一條指令必須有確切的含義，對于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過已經(jīng)實現(xiàn)的基本操作執(zhí)行有限次來實現(xiàn)。1.4算法及算法分析1.4算法及算法分析“好”算法的衡量指標正確性能解決問題，獲得正確結果健壯性（魯棒性）簡單性容易理解和實現(xiàn)抽象分級：如將算法分成多個模塊，每個模塊又可細分方便好用和可讀性強：人類短期記憶的對象數(shù)=7±2個高效性時間和空間效率

歐幾里德算法（有窮性、確定性、可行性）mnr算法的例：歐幾里德算法——輾轉相除法求兩個自然數(shù)m

和n

的最大公約數(shù)1.4算法及算法分析算法的描述方法——自然語言優(yōu)點：容易理解缺點：冗長、二義性使用方法：粗線條描述算法思想

注意事項：避免寫成自然段1.4算法及算法分析步驟1：將m除以n得到余數(shù)r；步驟2：若r等于0，則n為最大公約數(shù)，算法結束；否則執(zhí)行步驟3；步驟3：將n的值放在m中，將r的值放在n中，重新執(zhí)行步驟1；例：歐幾里德算法自然語言1.4算法及算法分析優(yōu)點：流程直觀缺點：缺少嚴密性、靈活性使用方法：描述簡單算法注意事項：注意抽象層次?？砂闯橄髮哟畏旨壝枋鏊惴ǖ拿枋龇椒ā鞒虉D1.4算法及算法分析N開始輸入m和n

r=m%nr=0m=n；n=r輸出n結束Y流程圖例：歐幾里德算法1.4算法及算法分析優(yōu)點：能由計算機執(zhí)行缺點：抽象性差，對語言要求高使用方法：算法需要驗證注意事項：將算法寫成子函數(shù)。按抽象層次分級——算法函數(shù)用下一層的子函數(shù)描述算法的描述方法——程序設計語言1.4算法及算法分析#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}程序設計語言例：歐幾里德算法1.4算法及算法分析偽代碼（Pseudocode）：介于自然語言和程序設計語言之間的方法，它采用某一程序設計語言的基本語法，操作指令可以結合自然語言來設計。優(yōu)點：表達能力強，抽象性強，容易理解使用方法：7±2——抽象分級算法的描述方法——偽代碼1.4算法及算法分析1.r=m%n;2.循環(huán)直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.輸出n;偽代碼上述偽代碼再具體一些，用C++的函數(shù)來描述。例：歐幾里德算法1.4算法及算法分析intCommonFactor(intm,intn){r=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}1.4算法及算法分析對C++語言進行了如下簡化：⑴局部變量可以不聲明；⑵寫出子函數(shù)即可，子函數(shù)不用在主函數(shù)中調用，省略主函數(shù)；⑶所有的包含函數(shù)（頭函數(shù).h）可以省略；⑷交換兩個變量的語句可以簡寫為a←→b。算法分析度量算法效率的方法：

事后統(tǒng)計：將算法實現(xiàn)，測算其時間和空間開銷。

缺點：⑴編寫程序實現(xiàn)算法將花費較多的時間和精力；⑵所得實驗結果依賴于計算機的軟硬件等環(huán)境因素。

事前分析：對算法所消耗資源的一種估算方法。1.4算法及算法分析1.4算法及算法分析方法在算法中的某些部位插裝時間函數(shù)time()測定算法在一組已給輸入下完成某一功能所花費的時間事后統(tǒng)計測定順序搜索算法seqsearch的效率

行

int

seqsearch(

inta[],

constintn,

constintx)

//a[0],…,a[n-1]

1

{

2

inti=0;

3

while(i<n

&&a[i]!=x)

4

i++;

5

if(i==n)return-1;

6

return

i;

7

}1.4算法及算法分析事后統(tǒng)計的例——順序搜索(SequenialSearch)插裝time()的計時程序

void

TimeSearch()

{//在1到1000中搜索0

inta[1001],n[20];//n[i]存放要搜索的元素個數(shù)

for

(

intj=1;j<=1000;j++)

a[j]=j;//a[1]=1,a[2]=2,…

for(j=0;j<10;j++)

{

n[j]=10*j;//n[0]=0,n[1]=10,n[2]=20

n[j+10]=100*(j+1);

}//n[10]=100,n[11]=200,n[12]=300...cout

<<"ntime"<<

endl;

for

(j=0;j<20;j++){

long

start,stop;

time(start);

int

k=seqsearch(a,n[j],0);

time(stop);

longrunTime=stop-start;

cout

<<""<<n[j]<<""<< runTime<<

endl;

}

cout

<<"Timesareinhundredthsofa second."<<

endl;}程序測試結果輸出測定順序搜索算法的效率

——插裝時間函數(shù)time()后就行了？

改進的計時程序void

TimeSearch()

{inta[1001],n[20];

constlongr[20]={300000,300000,200000,200000,100000,100000,100000,80000,80000,50000,50000,25000,15000,15000,10000,7500,7000,6000,5000,5000};

for(

intj=1;j<=1000;j++)

a[j]=j;

for(j=0;j<10;j++){

n[j]=10*j;n[j+10]=100*(j+1);

}cout<<"ntotalTimerunTime"<<

endl;for

(j=0;j<20;j++){

long

start,stop;

time(start);

//開始計時

for(

longb=1;b<=r[j];b++)

intk=seqsearch(a,n[j],0

);

//執(zhí)行r[j]次

time(stop);

//停止計時

longtotalTime=stop-start;

float

runTime=

(float)(totalTime)/(float)(r[j]);

cout

<<""<<n[j]<<""<<totalTime<<""<<runTime<<

endl;

}}程序測試結果輸出算法分析算法分析（AlgorithmAnalysis）：對算法所需要的計算機資源——時間和空間進行（事前）估算。時間復雜性（TimeComplexity）空間復雜性（SpaceComplexity）1.4算法及算法分析算法的時間復雜度分析1.4算法及算法分析算法分析算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間指令系統(tǒng)、編譯的代碼質量單位時間每條語句執(zhí)行次數(shù)之和for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語句的執(zhí)行次數(shù)問題規(guī)模：輸入量的多少?；菊Z句：是執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令。for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;問題規(guī)模：n基本語句：x++1.4算法及算法分析算法分析空間復雜度

當問題規(guī)模由1增至n時，算法所需空間也由S(1)增至S(n)（按某個單位計算），則S(n)稱為此算法的空間復雜度時間復雜度

當問題規(guī)模由1增至n時，算法所耗時間也由T(1)增至T(n)（按某個單位計算），則T(n)稱為此算法的時間復雜度問題規(guī)模：輸入量的多少。1.4算法及算法分析算法分析空間復雜度估算存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結構成分、對象的數(shù)據(jù)成員等)變量所占的空間可變部分

尺寸與實例特性有關的成分變量所占空間、引用變量所占空間、遞歸棧所用的空間、通過new和delete命令動態(tài)使用的空間例：floatabc(floata,floatb,floatc){returna+b+b*c+(a+b-c)/(a+b)}

//占用的空間數(shù)為常數(shù)floatsum(floata[],constintn){floats=0.0;for(inti=0;i<n;i++)s+=a[i];returns;}

//占用的空間數(shù)為常數(shù);數(shù)組a[]在此函數(shù)中僅占用一個空間(首地址)floatrsum(floata[],constintn){if(n<=0)return0;elsereturnrsum(a,n-1)+a[n-1];}

//占用的空間數(shù)為4(n+1);此為遞歸函數(shù)，深度=n+1，每層保留兩個參數(shù)、函數(shù)返回值和返回地址共四個存儲單位時間復雜度估算算法指令的執(zhí)行時間程序步語法上或語義上有意義的一段指令序列執(zhí)行時間與實例特性無關例如：

注釋：程序步數(shù)為0

聲明語句：程序步數(shù)為0

表達式：程序步數(shù)為1程序步確定方法

1）插入計數(shù)全局變量count（稱為插樁）

2）建表，列出每個語句的程序步

例以迭代方式求累加和的函數(shù)行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(inti=0;i<n;i++)

4s+=a[i];

5

returns;

6

} 在求累加和程序中加入count語句

floatsum(

floata[],constintn){floats=0.0;count++; //count統(tǒng)計執(zhí)行語句條數(shù)

for(

inti=0;i<n;i++)

{

count++; //針對for語句

s+=a[i]; count++;//針對賦值語句

}

count++;//針對for的最后一次

count++;

//針對return語句

returns;}

//執(zhí)行結束得程序步數(shù)count=2*n+3注意：例如：賦值語句

x=sum(R,n);

本身的程序步數(shù)為1；

一次執(zhí)行對函數(shù)

sum(R,n)的調用需要的程序步數(shù)為2*n+3；

一次執(zhí)行的程序步數(shù)為 1+2*n+3=2*n+4■不同語句的執(zhí)行時間不同，但是如果它們的執(zhí)行時間差一個與實例特性無關(包括與問題規(guī)模無關)的常數(shù)時，仍將它們看成一樣的程序步。由此，最終結果也差常數(shù)倍。

■一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)——可能與問題規(guī)模有關。程序步數(shù)計算工作表格時間復雜度估算有時我們僅估算算法中某一種運算(操作)的數(shù)目：加減法數(shù)目，乘除法數(shù)目數(shù)據(jù)交換或移動的次數(shù)定義

若存在兩個正的常數(shù)c和n0，對于任意n≥n0，都有|T(n)|≤c×f(n)，則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關緊要T(n)c×f(n)當問題規(guī)模充分大時在漸近意義下的階。1.4算法及算法分析算法分析——大O符號（大O表示法

）加法規(guī)則

針對并列程序段

T(n,m)=T1(n)+T2(m)=O(f(n))+O(g(m)) =O(max(f(n),g(m)))

=O(f(n)+g(m))

乘法規(guī)則

針對嵌套程序段

T(n,m)=T1(n)*T2(m)=O(f(n))*O(g(m))

=O(f(n)*g(m))漸進的空間復雜度(記號同時間)

S(n)=O(f(n))

算法分析——大O符號（大O表示法

）運算規(guī)則1.4算法及算法分析定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個m次多項式，且m是與n無關的常數(shù)，則A(n)=O(nm)。說明：在計算算法時間復雜度時，可以忽略所有低次冪和最高次冪的系數(shù)。1.4算法及算法分析算法分析——大O符號例1-5

++x;例1-6

for(i=1;i<=n;++i)++x;例1-7for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;

例1-8for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;1.4算法及算法分析算法分析例1-9for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)