緒論數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)與算法主講：和薇辦公室:綜合樓210

答疑時(shí)間：周二中午12：30-16：00Ifyougivesomeoneaprogram,youwillfrustratethemforaday;Ifyouteachthemhowtoprogram,youwillfrustratethemforalifetime.人機(jī)對(duì)奕問題……..……..…...…...…...…...數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計(jì)NicklausWirth，1934年出生于瑞士，1963年在加州大學(xué)伯克利分校取得博士學(xué)位。取得博士學(xué)位后直接被以高門檻著稱的斯坦福大學(xué)聘到剛成立的計(jì)算機(jī)科學(xué)系工作。在斯坦福大學(xué)成功的開發(fā)出AlgolW以及PL360后，愛國(guó)心極強(qiáng)的NicklausWirth于1967年回到祖國(guó)瑞士，第二年在他的母校蘇黎世工學(xué)院他創(chuàng)立與實(shí)現(xiàn)了Pascal語(yǔ)言——當(dāng)時(shí)世界上最受歡送的語(yǔ)言之一。憑借一句話獲得圖靈獎(jiǎng)的Pascal之父——NicklausWirth，讓他獲得圖靈獎(jiǎng)的這句話就是他提出的著名公式：“算法+數(shù)據(jù)結(jié)構(gòu)=程序〞。這個(gè)公式對(duì)計(jì)算機(jī)科學(xué)的影響程度足以類似物理學(xué)中愛因斯坦的“E=MC^2〞——一個(gè)公式展示出了程序的本質(zhì)。數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計(jì)問題〔problem〕:從輸入到輸出的一種映射函數(shù)。數(shù)據(jù)結(jié)構(gòu)〔datastructure〕:邏輯數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)的存儲(chǔ)表達(dá)，支持相應(yīng)的操作。算法〔algorithm〕:對(duì)待定問題求解過程的描述方法。程序〔program〕：算法在計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言中的實(shí)現(xiàn)。給定問題設(shè)計(jì)求解問題的算法抽象出數(shù)據(jù)，建立數(shù)據(jù)結(jié)構(gòu)將算法分解成對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算對(duì)算法的性能進(jìn)行評(píng)估編程實(shí)現(xiàn)，并上機(jī)調(diào)試交付使用滿意？正確？對(duì)算法不滿意對(duì)數(shù)據(jù)結(jié)構(gòu)不滿意不滿意滿意正確有錯(cuò)初級(jí)算法數(shù)據(jù)結(jié)構(gòu)級(jí)算法算法分析問題求解的大致步驟課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的專業(yè)根底課公共根底課、專業(yè)根底課、專業(yè)選修課在教學(xué)方案中的地位：核心、承上啟下前導(dǎo)課：高等數(shù)學(xué)、離散數(shù)學(xué)、程序設(shè)計(jì)語(yǔ)言后續(xù)課：數(shù)據(jù)庫(kù)、操作系統(tǒng)、編譯原理……編譯技術(shù)要使用棧、散列表及語(yǔ)法樹操作系統(tǒng)中用隊(duì)列、存儲(chǔ)管理表及目錄樹數(shù)據(jù)庫(kù)系統(tǒng)運(yùn)用線性表、多鏈表、及索引樹etc教學(xué)目的掌握根本的常用數(shù)據(jù)結(jié)構(gòu)的ADT及其應(yīng)用學(xué)會(huì)合理地組織數(shù)據(jù)，有效地表示數(shù)據(jù)，有效地處理數(shù)據(jù)根本掌握算法的設(shè)計(jì)分析技術(shù)提高程序設(shè)計(jì)的質(zhì)量教學(xué)目的數(shù)據(jù)結(jié)構(gòu)概念程序?qū)崿F(xiàn)實(shí)際問題數(shù)據(jù)結(jié)構(gòu)抽象考核方式平時(shí)作業(yè)+出勤20%上機(jī)練習(xí)+課堂提問+一周外教學(xué)習(xí)效果30%期末50%第一章緒論1938年出生，25歲畢業(yè)于加州理工學(xué)院數(shù)學(xué)系，博士畢業(yè)后留校任教，28歲任副教授。30歲時(shí)，加盟斯坦福大學(xué)計(jì)算機(jī)系，任教授。從31歲起，開始出版他的歷史性經(jīng)典巨著：TheArtofComputerProgramming他方案共寫7卷，然而出版三卷之后，已震驚世界，使他獲得計(jì)算機(jī)科學(xué)界的最高榮譽(yù)圖靈獎(jiǎng)，此時(shí)，他年僅36歲。數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——克努特?cái)?shù)據(jù)結(jié)構(gòu)的根本概念抽象數(shù)據(jù)類型算法描述算法分析本章的根本內(nèi)容是：一、數(shù)據(jù)結(jié)構(gòu)的根本概念數(shù)據(jù)描述客觀事物的數(shù)字、字符以及一切能夠輸入到計(jì)算機(jī)中，并且能夠被計(jì)算機(jī)程序處理的符號(hào)的集合。

數(shù)據(jù)元素?cái)?shù)據(jù)的根本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行處理。結(jié)構(gòu)數(shù)據(jù)元素之間具有的關(guān)系數(shù)據(jù)結(jié)構(gòu)

1.數(shù)據(jù)結(jié)構(gòu)就是具有結(jié)構(gòu)的數(shù)據(jù)元素的集合。2.數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組B=(D,R)其中，B表示數(shù)據(jù)結(jié)構(gòu)，D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系的集合。一、數(shù)據(jù)結(jié)構(gòu)的根本概念數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次:是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的抽象描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在這個(gè)集合上的若干關(guān)系來描述。邏輯結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念問題1：怎樣理解數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)?數(shù)據(jù)元素之間存在著“一對(duì)一〞的線性關(guān)系根據(jù)數(shù)據(jù)元素之間存在的邏輯關(guān)系的不同數(shù)學(xué)特性，通常有以下4種數(shù)據(jù)結(jié)構(gòu):①線性結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念

001003002004006005008007如：學(xué)生根本情況表的圖示表示例

飛機(jī)訂票系統(tǒng)?？蛻羰紫炔樵兒桨嘈畔⒈恚⒏鶕?jù)自己的情況按照起始城市和起降時(shí)間查找具體航班，進(jìn)行訂票操作?？蛻糨斎胄彰?、證件號(hào)等信息后，選擇航班、訂票數(shù)，即可完成訂票。在此類系統(tǒng)中，計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系。數(shù)據(jù)元素之間存在著“一對(duì)多〞的樹形關(guān)系②樹形結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念如：文件目錄間的樹型關(guān)系例2：物料清單〔BOM，BillofMaterial〕是一種描述配套件結(jié)構(gòu)的零件表，其中包括所有子件、零件、原材料的清單，以及制造一個(gè)配件所需要的所有物料的數(shù)量。BOM是制造業(yè)信息系統(tǒng)的一個(gè)核心部件。如果我們將產(chǎn)品的配件按照線性數(shù)據(jù)結(jié)構(gòu)羅列表示，如圖(a)所示，將不利于產(chǎn)品的設(shè)計(jì)和改進(jìn)；當(dāng)把產(chǎn)品的配件按照一定的層次進(jìn)行表示時(shí)，如圖(b)所示，形成的結(jié)構(gòu)圖像一棵倒長(zhǎng)的樹，“樹根〞是該產(chǎn)品，而所有的“葉子〞就是產(chǎn)品對(duì)應(yīng)的零配件?！岸鄬?duì)多〞關(guān)系③圖狀或網(wǎng)狀結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念如：航空網(wǎng)絡(luò)例：郵遞員送信問題?，F(xiàn)在郵遞員從郵局出發(fā)，向以下幾個(gè)地點(diǎn)2、3、4送信。要求選擇一條路線，從郵局出發(fā)，經(jīng)過每個(gè)地點(diǎn)，最終回到郵局，并且路線長(zhǎng)度最短。

該問題描述的是經(jīng)典的“中國(guó)郵路〞問題，通常這類郵件發(fā)送問題的數(shù)學(xué)模型是一種稱為“圖〞的數(shù)據(jù)結(jié)構(gòu)。在此例中可以用一個(gè)頂點(diǎn)表示一個(gè)地點(diǎn)，用兩點(diǎn)之間的連線表示兩地之間的通路。數(shù)據(jù)元素除“同屬一個(gè)集合〞的關(guān)系外，別無(wú)其他關(guān)系④純集合結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念是對(duì)數(shù)據(jù)元素之間的邏輯關(guān)系的抽象描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在這個(gè)集合上的假設(shè)干關(guān)系來描述。如：B=(D,R)

其中，B表示數(shù)據(jù)結(jié)構(gòu)，D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系的集合。邏輯結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念例:家族的族譜JIACBDHGFE

D={A，B，C，D，E，F(xiàn)，G，H，I，J}R={<A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè)某家族有10個(gè)成員A，B，C，D，E，F(xiàn)，G，H，I，J，他們之間的血緣關(guān)系可以用如以下圖表示。具有某種邏輯結(jié)構(gòu)的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式(存儲(chǔ)映象)。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次:存儲(chǔ)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念計(jì)算機(jī)主存儲(chǔ)器的特性：其存儲(chǔ)空間提供了一種具有非負(fù)整數(shù)地址編碼的，相鄰單元的集合，其根本的存儲(chǔ)單元是字節(jié)。計(jì)算機(jī)的指令具有按地址隨機(jī)訪問存儲(chǔ)空間內(nèi)任意單元的能力，訪問不同地址所需的時(shí)間根本相同。具有某種邏輯結(jié)構(gòu)的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式(存儲(chǔ)映象)。數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩個(gè)層次:存儲(chǔ)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)問題2：怎樣理解順序和鏈?zhǔn)絻煞N存儲(chǔ)結(jié)構(gòu)?一、數(shù)據(jù)結(jié)構(gòu)的根本概念用一組地址連續(xù)的存儲(chǔ)單元依次存放數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過元素的地址直接反映。順序存儲(chǔ)結(jié)構(gòu)一、數(shù)據(jù)結(jié)構(gòu)的根本概念用一組地址任意的存儲(chǔ)單元依次存放數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過指針間接地反映。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)a1a2a3

a30…d1d2d3d4

…d30a2a1a3a4a30存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu)線性結(jié)構(gòu)〔線性表〕劉曉光馬廣生王民…張玉華男男…女男漢回壯…漢161721…25……………

姓名性別民族年齡其他

例2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)…d1d2d3d4

a1a2a3a30∧head…a2a1a4a3d4d1d5d3

1.

研究數(shù)據(jù)元素之間的客觀聯(lián)系。

2.

研究具有某種邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的存儲(chǔ)方式。3.研究如何在數(shù)據(jù)的各種結(jié)構(gòu)(邏輯的和物理的)的根底上對(duì)數(shù)據(jù)實(shí)施一系列有效的根本操作。邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程研究的主要內(nèi)容算法數(shù)據(jù)類型規(guī)定了程序?qū)?shù)據(jù)的取值范圍和對(duì)其的操作，按數(shù)據(jù)類型的“值〞的不同特性，可分為：原子類型——不可分的非結(jié)構(gòu)類型結(jié)構(gòu)類型——可分的類型二、抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型，簡(jiǎn)稱ADT。定義了一個(gè)數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象中各元素間的結(jié)構(gòu)關(guān)系以及一組處理數(shù)據(jù)的操作。二、抽象數(shù)據(jù)類型數(shù)學(xué)模型非形式算法抽象數(shù)據(jù)類型偽語(yǔ)言程序數(shù)據(jù)結(jié)構(gòu)可執(zhí)行程序抽象數(shù)據(jù)類型最重要的特點(diǎn)是數(shù)據(jù)抽象和信息隱藏。對(duì)抽象數(shù)據(jù)類型的定義方法：ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：根本操作：}ADT抽象數(shù)據(jù)類型名二、抽象數(shù)據(jù)類型Request()Retrieve()Return()界面實(shí)現(xiàn)管理書庫(kù)9頁(yè)三、算法及其描述1.算法的定義算法是為解決一個(gè)或一類問題而給出的一個(gè)確定的有限長(zhǎng)的操作序列。如：求兩個(gè)正整數(shù)m，n中的最大數(shù)MAX的算法。

〔1〕假設(shè)m>n那么max=m

〔2〕假設(shè)m<=n那么max=n問題3：算法和程序的區(qū)別?三、算法及其描述2.基本算法

1.枚舉法2.歸納法

3.回溯法

4.模擬法

5.貪心法6.動(dòng)態(tài)規(guī)劃法…求解百雞問題x+y+z=1005x+3y+z/3=100求1+2+3+…+100=？公式：

=n(n+1)/2求迷宮通路以及圖的遍歷建立模擬數(shù)據(jù)模型進(jìn)行求解三、算法及其描述3.算法的描述

1.自然語(yǔ)言2.流程圖

3.偽代碼

4.計(jì)算機(jī)語(yǔ)言

歐幾里德算法mnr例：歐幾里德算法——輾轉(zhuǎn)相除法求兩個(gè)自然數(shù)m

和n

的最大公約數(shù)三、算法及其描述4.算法的性質(zhì)

1.可行性2.確定性

3.有窮性

4.有輸入

5.有輸出6.正確性7.可讀性8.可維護(hù)性9.健壯性10.時(shí)間效率高、

存儲(chǔ)量低11.…各時(shí)間量級(jí)在現(xiàn)實(shí)中對(duì)應(yīng)的物體速度米/秒英制度量衡現(xiàn)實(shí)世界的例子10-1110-1010-910-810-710-610-510-410-310-210-111011021031041051061071081.2英寸/世紀(jì)1.2英寸/十年1.2英寸/年1英尺/年1英尺/月3.4英寸/天1.4英寸/時(shí)1.2英尺/時(shí)2英寸/分2英尺/分20英尺/分2.2英里/時(shí)22英里/時(shí)220英里/時(shí)37英里/分370英里/分3700英里/分620英里/秒6200英里/秒62,000英里/秒鐘乳石的生長(zhǎng)速度大陸板塊的漂移速度指甲的生長(zhǎng)速度頭發(fā)的生長(zhǎng)速度雜草的生長(zhǎng)速度冰河的流動(dòng)速度表的分針轉(zhuǎn)動(dòng)速度胃腸的蠕動(dòng)速度蝸牛的速度螞蟻的速度巨龜?shù)乃俣热祟惖纳⒉剿俣热祟惣才芩俣嚷菪龢w機(jī)的速度噴氣式飛機(jī)的速度宇宙飛船的速度流星撞擊地球的速度地球自轉(zhuǎn)速度衛(wèi)星從洛杉磯到紐約的速度光速的三分之一5、算法效率的度量方法是騾子是馬，拉出來遛遛。事后統(tǒng)計(jì)事前分析——必須事先編制好程序；——依賴硬件、軟件等環(huán)境；——測(cè)試數(shù)據(jù)設(shè)計(jì)困難等算法一：intmax1(intarray,intsize,intd){intmax=0,i;for(i=0;i<size;++i)array[i]*=d;for(i=0;i<size;++i)if(array[i]>max)max=array[i];returnmax;}算法二：intmax2(intarray,intsize,intd){intmax=0,i;for(i=0;i<size;++i)if(array[i]>max)max=array[i];returnmax*d;}5、算法效率的度量方法1.6、算法的復(fù)雜度

2.編寫程序所采用的計(jì)算機(jī)語(yǔ)言。4.機(jī)器執(zhí)行一條指令的時(shí)間長(zhǎng)短。1.問題的規(guī)模。

一個(gè)程序在計(jì)算機(jī)中的執(zhí)行效率與諸多因素有關(guān)，其中主要有：

3.源程序編譯的強(qiáng)弱以及所產(chǎn)生的機(jī)器代碼質(zhì)量的優(yōu)劣。時(shí)間復(fù)雜度空間復(fù)雜度假設(shè)問題規(guī)模，即輸入量的大小，用n表示。依據(jù)算法編出程序之后，運(yùn)行程序在計(jì)算機(jī)消耗的時(shí)間，用T(n)表示。T(n)=O(f(n))

依據(jù)算法編出程序之后，在計(jì)算機(jī)占用的存儲(chǔ)單元的總數(shù)，用S(n)表示。

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

6、算法的復(fù)雜度大O表示法算法中根本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作T(n)=O(f(n))。大O表示法表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同。稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。技巧：只求出T(n)的最高階，忽略其最低項(xiàng)和常系數(shù)。一個(gè)簡(jiǎn)單的例子計(jì)算的一個(gè)簡(jiǎn)單程序

intsum(intN){inti,psum;聲明不計(jì)時(shí)間psum=0;占一個(gè)時(shí)間單元for(i=1;i<=N;i++)psum+=i*i*i;returnpsum;占一個(gè)時(shí)間單元}每執(zhí)行一次占用4個(gè)時(shí)間單元(2次乘，1次法，1次賦值)，共執(zhí)行N次，占用4N個(gè)時(shí)間單元初始化占1個(gè)時(shí)間單元，測(cè)試占N+1個(gè)時(shí)間單元，自增占N個(gè)單元，共占用2N+2個(gè)時(shí)間單元共占用6N+4個(gè)時(shí)間單元，故該函數(shù)的算法復(fù)雜度是O(N)大O表示法的一般法那么法那么一：for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語(yǔ)句〔包括測(cè)試〕的運(yùn)行時(shí)間乘以迭代的次數(shù)。例下面是一段對(duì)數(shù)組中的各個(gè)元素求和的代碼：for(i=sum=0;i<n;i++〕 sum+=a[i];求該算法的時(shí)間復(fù)雜度其中主要的操作為賦值運(yùn)算，故該算法的時(shí)間代價(jià)主要表達(dá)在賦值操作的數(shù)目上在循環(huán)開始之前有兩次賦值，分別對(duì)i和對(duì)sum進(jìn)行；循環(huán)進(jìn)行了n次，每次循環(huán)中執(zhí)行兩次賦值，分別對(duì)sum和對(duì)i進(jìn)行更新操作，共執(zhí)行了2n次；總共有2+2n次賦值操作。其時(shí)間復(fù)雜度為O(n)法那么一：for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語(yǔ)句〔包括測(cè)試〕的運(yùn)行時(shí)間乘以迭代的次數(shù)。大O表示法的一般法那么法那么一：for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語(yǔ)句〔包括測(cè)試〕的運(yùn)行時(shí)間乘以迭代的次數(shù)。法那么二：在一組嵌套for循環(huán)內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以所有的for循環(huán)的大小的乘積。依次求出給定數(shù)組的所有子數(shù)組中各元素之和：for(i=0;i<n;i++) for(j=1,sum=a[0];j<=i;j++)

sum+=a[j];循環(huán)開始前，有一次對(duì)i的賦值操作。外層循環(huán)共進(jìn)行n次，每個(gè)循環(huán)中包含一個(gè)內(nèi)層循環(huán)，以及對(duì)i,j,sum分別進(jìn)行賦值操作；每個(gè)內(nèi)層循環(huán)執(zhí)行2個(gè)賦值操作，分別更新sum和j；共執(zhí)行i次〔i=1,2,…,n-1〕。整個(gè)程序總共執(zhí)行的賦值操作為：例法那么二：在一組嵌套for循環(huán)內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以所有的for循環(huán)的大小的乘積。=O(n2)大O表示法的一般法那么法那么一：for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語(yǔ)句〔包括測(cè)試〕的運(yùn)行時(shí)間乘以迭代的次數(shù)。法那么二：在一組嵌套for循環(huán)內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以所有的for循環(huán)的大小的乘積。法那么三：對(duì)于順序語(yǔ)句，將各語(yǔ)句的運(yùn)行時(shí)間求和即可。意味著其中的最大值就是所得的運(yùn)行時(shí)間。for(i=sum=0;i<n;i++〕 sum+=a[i];for(i=0;i<n;i++) for(j=1,sum=a[0];j<=i;j++) sum+=a[j];第一個(gè)for循環(huán)用去O(n)第二個(gè)for循環(huán)用去O(n2)整個(gè)程序開銷為O(n2)例法那么三：對(duì)于順序語(yǔ)句，將各語(yǔ)句的運(yùn)行時(shí)間求和即可。意味著其中的最大值就是所得的運(yùn)行時(shí)間。大O表示法的一般法那么法那么一：for循環(huán)的運(yùn)行時(shí)間至多是該for循環(huán)內(nèi)語(yǔ)句〔包括測(cè)試〕的運(yùn)行時(shí)間乘以迭代的次數(shù)。法那么二：在一組嵌套for循環(huán)內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以所有的for循環(huán)的大小的乘積。法那么三：對(duì)于順序語(yǔ)句，將各語(yǔ)句的運(yùn)行時(shí)間求和即可。意味著其中的最大值就是所得的運(yùn)行時(shí)間。法那么四：一個(gè)if(condition)S1elseS2語(yǔ)句的運(yùn)行時(shí)間從不超過判斷再加上S1和S2中運(yùn)行時(shí)間長(zhǎng)者的總的運(yùn)行時(shí)間大O表示法的一般法那么法那么五：一個(gè)沒有循環(huán)的算法的根本運(yùn)算次數(shù)與問題規(guī)模n無(wú)關(guān)，記做O(1)，也稱作常數(shù)階。如語(yǔ)句x=x+1;其復(fù)雜度為O(1)。法那么六：一個(gè)算法所執(zhí)行的根本運(yùn)算次數(shù)常常因輸入不同而異。算法執(zhí)行的根本運(yùn)算次數(shù)不僅取決于問題規(guī)模，也與輸入數(shù)據(jù)的性質(zhì)有關(guān)。如：voidfun(inta[],intn,intk){inti;i=0;//語(yǔ)句1

while(i<n&&a[i]!=k)//語(yǔ)句2i++;//語(yǔ)句3returni;//語(yǔ)句4}語(yǔ)句3的頻度不僅與問題規(guī)模n有關(guān)，還與輸入實(shí)例中a的各元素取值以及k的取值相關(guān)，假設(shè)a中沒有與k相等的元素，那么語(yǔ)句頻度為n，假設(shè)a中的第一個(gè)元素a[0]=k，那么語(yǔ)句3的頻度為0。故可用最壞情況下的時(shí)間復(fù)雜度作為時(shí)間復(fù)雜度，記做T(n)=O(n)例法那么六：一個(gè)算法所執(zhí)行的根本運(yùn)算次數(shù)常常因輸入不同而異。算法執(zhí)行的根本運(yùn)算次數(shù)不僅取決于問題規(guī)模，也與輸入數(shù)據(jù)的性質(zhì)有關(guān)。voidfun(inta[],intn,intk){inti;i=0;//語(yǔ)句1while(i<n&&a[i]!=k)//語(yǔ)句2i++;//語(yǔ)句3returni;//語(yǔ)句4}此例也可以選擇算法的期望或平均時(shí)間復(fù)雜度作為討論目標(biāo)。所謂平均時(shí)間復(fù)雜度是指所有可能的輸入都是以等概率出現(xiàn)的情況下的期望運(yùn)行時(shí)間與問題規(guī)模n的數(shù)量級(jí)的關(guān)系，即k出現(xiàn)在任何位置的概率都為1/n，那么語(yǔ)句的平均執(zhí)行頻度為[0+1+2+…+(n+1)]/n=(n-1)/2，故T(n)=O(n)。例法那么六：一個(gè)算法所執(zhí)行的根本運(yùn)算次數(shù)常常因輸入不同而異。算法執(zhí)行的根本運(yùn)算次數(shù)不僅取決于問題規(guī)模，也與輸入數(shù)據(jù)的性質(zhì)有關(guān)。常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)：O(1),O(n),O(n2),O(n3),O(log2n),O(nlog2n),O(2n),O(n!)nlog2nnlog2nn2n32nn!1001121212