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

數(shù)據(jù)結(jié)構(gòu)》主講教師陳明

教材

數(shù)據(jù)結(jié)構(gòu)教程

李春葆等

清華大學(xué)出版社

參考教材數(shù)據(jù)結(jié)構(gòu)（C++語言版）

劉清王瓊電子工業(yè)出版社數(shù)據(jù)結(jié)構(gòu)（C語言版）

嚴(yán)蔚敏吳偉民清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)—C++語言描述（影印版）RobertL.Kruse，AlexanderJ.Ryba高等教育出版社教學(xué)內(nèi)容

第一章緒論

第二章線性表

第三章棧和隊(duì)列

第四章串（最后選講）

第五章數(shù)組和廣義表（簡單介紹）

第六章樹

第七章圖

第八章查找

第九章排序課程特點(diǎn)及教學(xué)方法難度大綜合性強(qiáng)必須下苦功學(xué)習(xí)關(guān)于教學(xué)的幾個(gè)新觀念教學(xué)過程以學(xué)生為主體,教師為主導(dǎo)學(xué)生由知識技能的被動接受者向知識技能的主動探求者轉(zhuǎn)變,教師由傳授者向教學(xué)活動的設(shè)計(jì)者、組織者、指導(dǎo)者轉(zhuǎn)變教學(xué)目標(biāo)為使學(xué)生在知識、能力、素質(zhì)方面協(xié)調(diào)發(fā)展能力包括自學(xué)能力、知識運(yùn)用能力、動手能力、創(chuàng)新能力、發(fā)現(xiàn)問題能力、分析問題和解決問題能力以及可持續(xù)發(fā)展能力第一章緒論

第一章緒論

1.1

本課程的研究對象；

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；

1.3數(shù)據(jù)結(jié)構(gòu)的分類及表示；

1.4算法及算法分析（算法評價(jià)）

1.1本課程研究的問題

計(jì)算機(jī)的發(fā)展

軟件硬件應(yīng)用領(lǐng)域

數(shù)據(jù)處理的種類和能力

數(shù)據(jù)數(shù)值數(shù)據(jù)

非數(shù)值數(shù)據(jù)

數(shù)(整數(shù),實(shí)數(shù))字符字符串文字圖形圖象聲音數(shù)據(jù)：客觀對象的符號表示數(shù)學(xué)中的整數(shù)、實(shí)數(shù)，

課程名，地名、書名程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)

數(shù)值問題與非數(shù)值問題1）數(shù)值問題例1已知：游泳池的長len和寬wide，求面積area◆設(shè)計(jì)求解問題的方法◆

編程1.1本課程研究的問題◆建模型：

問題涉及的對象：游泳池的長len

寬wide，面積area；

對象之間的關(guān)系：area=len

wide

學(xué)號姓名性別出生日期籍貫入學(xué)成績所在班級 00201

楊潤生男82/06/01廣州56100計(jì)算機(jī)2

00102石磊男83/12/21汕頭51200計(jì)算機(jī)1

00202李梅女83/02/23陽江53200計(jì)算機(jī)200301馬耀先男82/07/12廣州50900計(jì)算機(jī)32）非數(shù)值問題例2已知某級學(xué)生情況,要求分班按入學(xué)成績排列順序。1.1本課程研究的問題在這類文檔管理的數(shù)學(xué)模型中,計(jì)算機(jī)處理的對象之間通常存在著一種最簡單的線性關(guān)系,這類數(shù)學(xué)模型稱為線性模型。1.1本課程研究的問題例3迷宮問題。在迷宮中，每走到一處，接下來可走的通路有三條。計(jì)算機(jī)處理的這類對象之間通常不存在線性關(guān)系。若把從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得一棵“樹”

入口

出口城市間交通網(wǎng)問題1.1本課程研究的問題數(shù)據(jù)結(jié)構(gòu)的研究問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲，如何處理。本課程討論的問題：應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，及如何表示,如何存儲，如何處理。

1.數(shù)據(jù)（Data）數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號集合。換句話說，數(shù)據(jù)是對客觀事物采用計(jì)算機(jī)能夠識別、存儲和處理的形式所進(jìn)行的描述。簡而言之，數(shù)據(jù)就是計(jì)算機(jī)化的信息。

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念例如對C源程序，數(shù)據(jù)概念不僅是源程序所處理的數(shù)據(jù)，相對于編譯程序來說，C編譯程序相對于源程序是一個(gè)處理程序，它加工的數(shù)據(jù)是字符流的源程序（.c），輸出的結(jié)果是目標(biāo)程序(.obj)；對于鏈接程序來說，它加工的數(shù)據(jù)是目標(biāo)程序(.obj)，輸出的結(jié)果是可執(zhí)行程序(.exe)，如圖1.1所示。圖1.1編譯程序示意圖源程序目標(biāo)程度可執(zhí)行程序C編譯程序C鏈接程序

2.數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位,是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。表1-1學(xué)籍表學(xué)號姓名性別籍貫出生年月住址101趙紅玲女河北1983.11北京………………數(shù)據(jù)項(xiàng)記錄

3.數(shù)據(jù)對象（DataObject）

數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對象是集合N={0，±1，±2，…}，字母字符數(shù)據(jù)對象是集合C={′A′，′B′，…，′Z′}，表1-1所示的學(xué)籍表也可看作一個(gè)數(shù)據(jù)對象。由此可看出，不論數(shù)據(jù)元素集合是無限集（如整數(shù)集）、有限集（如字符集），還是由多個(gè)數(shù)據(jù)項(xiàng)組成的復(fù)合數(shù)據(jù)元素（如學(xué)籍表），只要性質(zhì)相同，都是同一個(gè)數(shù)據(jù)對象。綜上1~3所述，再分析數(shù)據(jù)概念：

4.數(shù)據(jù)結(jié)構(gòu)（DataStructure）

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，圖1.2學(xué)校組織層次結(jié)構(gòu)圖圖1.3交通流量圖

5.數(shù)據(jù)類型(DataType)

數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合，即該類型的取值范圍，以及該類型中可允許使用的一組運(yùn)算。例如高級語言中的數(shù)據(jù)類型就是已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)例。從這個(gè)意義上講，數(shù)據(jù)類型是高級語言中允許的變量種類，是程序語言中已經(jīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)（即程序中允許出現(xiàn)的數(shù)據(jù)形式）。在高級語言中，整型類型可能的取值范圍是-32768~+32767，可用的運(yùn)算符集合為加、減、乘、除、乘方、取模（如C語言中+，-，*，/，%）。6.數(shù)據(jù)抽象與抽象數(shù)據(jù)類型１）數(shù)據(jù)的抽象計(jì)算機(jī)中使用的是二進(jìn)制數(shù)，匯編語言中則可給出各種數(shù)據(jù)的十進(jìn)制表示，如98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;使用者在編程時(shí)可以直接使用,不必考慮實(shí)現(xiàn)細(xì)節(jié)。在高級語言中，則給出更高一級的數(shù)據(jù)抽象，出現(xiàn)了數(shù)據(jù)類型，如整型、實(shí)型、字符型等。到抽象數(shù)據(jù)類型出現(xiàn)，可以進(jìn)一步定義更高級的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹、圖、窗口、管理器等，這種數(shù)據(jù)抽象的層次為設(shè)計(jì)者提供了更有利的手段，使得設(shè)計(jì)者可以從抽象的概念出發(fā)，從整體考慮，然后自頂向下、逐步展開，最后得到所需結(jié)果。可以這樣看，高級語言中提供整型、實(shí)型、字符、記錄、文件、指針等多種數(shù)據(jù)類型，可以利用這些類型構(gòu)造出像棧、隊(duì)列、樹、圖等復(fù)雜的抽象數(shù)據(jù)類型。２）抽象數(shù)據(jù)類型(AbstractDataType)

抽象數(shù)據(jù)類型（簡稱ADT）是指基于一類邏輯關(guān)系的數(shù)據(jù)類型以及定義在這個(gè)類型之上的一組操作。抽象數(shù)據(jù)類型的定義取決于客觀存在的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)如何表示和實(shí)現(xiàn)無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部使用。從某種意義上講，抽象數(shù)據(jù)類型和數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念。整數(shù)類型就是一個(gè)簡單的抽象數(shù)據(jù)類型實(shí)例?！俺橄蟆钡囊饬x在于教學(xué)特性的抽象。一個(gè)ADT定義了一個(gè)數(shù)據(jù)對象，數(shù)據(jù)對象中各元素間的結(jié)構(gòu)關(guān)系，以及一組處理數(shù)據(jù)的操作。ADT通常是指由用戶定義且用以表示應(yīng)用問題的數(shù)據(jù)模型，通常由基本的數(shù)據(jù)類型組成，并包括一組相關(guān)服務(wù)操作。抽象數(shù)據(jù)類型是近年來計(jì)算機(jī)科學(xué)中提出的最重要的概念之一，它集中體現(xiàn)了程序設(shè)計(jì)中一些最基本的原則：分解、抽象和信息隱藏。一個(gè)抽象數(shù)據(jù)類型確定了一個(gè)模型，但將模型的實(shí)現(xiàn)細(xì)節(jié)隱藏起來；它定義了一組運(yùn)算，但將運(yùn)算的實(shí)現(xiàn)過程隱藏起來。數(shù)學(xué)模型→抽象數(shù)據(jù)類型→數(shù)據(jù)結(jié)構(gòu)，恰好反應(yīng)了信息結(jié)構(gòu)轉(zhuǎn)換的三個(gè)重要階段，而在這個(gè)轉(zhuǎn)換過程中，數(shù)據(jù)結(jié)構(gòu)是基礎(chǔ)，抽象數(shù)據(jù)類型是中樞。

一個(gè)線性表的抽象數(shù)據(jù)類型的描述如下：

ADTLinear-list

數(shù)據(jù)元素所有ai屬于同一數(shù)據(jù)對象，i=1，2，…，n,n≥0；邏輯結(jié)構(gòu)所有數(shù)據(jù)元素ai（i=1，2，…，n-1）存在次序關(guān)系<ai，ai+1>，ai無前趨，an無后繼；操作 設(shè)L為Linear-list: Initial(L):初始化空線性表; Length(L):求線性表的表長; Get(L,i):取線性表的第i個(gè)元素；

Insert(L,i,b):在線性表的第i個(gè)位置插入元素b；

Delete(L,i):刪除線性表的第i個(gè)元素。３）抽象數(shù)據(jù)類型實(shí)現(xiàn)第一種情況：傳統(tǒng)的面向過程的程序設(shè)計(jì)。第二種情況：“包”、“模型”的設(shè)計(jì)方法。第三種情況：面向?qū)ο蟮某绦蛟O(shè)計(jì)（ObjectOriented Programming，簡稱OOP）。４）ADT的表示與實(shí)現(xiàn)

ADT的定義

ADT的定義格式不唯一,我們采用下述格式定義一個(gè)ADT:

ADT<ADT名>

{數(shù)據(jù)對象:<數(shù)據(jù)對象的定義>

結(jié)構(gòu)關(guān)系:<結(jié)構(gòu)關(guān)系的定義>

基本操作:<基本操作的定義>}ADT<ADT名>其中數(shù)據(jù)對象和結(jié)構(gòu)關(guān)系的定義采用數(shù)學(xué)符號和自然語言描述,而基本操作的定義格式為:<操作名稱>(參數(shù)表)

操作前提:<操作前提描述>

操作結(jié)果:<操作結(jié)果描述>關(guān)于參數(shù)傳遞

參數(shù)表中的參數(shù)有兩種：第一種參數(shù)只為操作提供待處理數(shù)據(jù),又稱值參；第二種參數(shù)既能為操作提供待處理數(shù)據(jù),又能返回操作結(jié)果，也稱變量參數(shù)。操作前提描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件,操作結(jié)果描述操作執(zhí)行之后,數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回結(jié)果。ADT可用現(xiàn)有計(jì)算機(jī)語言中已有的數(shù)據(jù)類型,即固有數(shù)據(jù)類型來表示和實(shí)現(xiàn)。不同語言的表示和實(shí)現(xiàn)方法不盡相同，如ADT中“返回結(jié)果的參數(shù)”，PASCAL語言用“變參”實(shí)現(xiàn),C++語言通過“引用型參數(shù)”實(shí)現(xiàn),而C語言用“指針參數(shù)”實(shí)現(xiàn)。用標(biāo)準(zhǔn)C++語言表示和實(shí)現(xiàn)ADT描述時(shí)，主要包括以下兩個(gè)方面:(1)通過結(jié)構(gòu)體將int、float等固有類型組合到一起,構(gòu)成一個(gè)結(jié)構(gòu)類型,再用typedef為該類型或該類型指針重新起一個(gè)名字。

(2)用C++語言函數(shù)實(shí)現(xiàn)各操作。基本操作主要有以下幾種：

(1)插入：在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素；

(2)刪除：刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定數(shù)據(jù)元素；

(3)更新：改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)元素的值，在概念上等價(jià)于刪除和插入操作的組合；

(4)查找：在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素（的位置和值)；

(5)排序：（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使數(shù)據(jù)元素按值由小到大或由大到小的次序排列。對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：

1）數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作；

2）數(shù)據(jù)的存儲結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；數(shù)據(jù)的邏輯結(jié)構(gòu)：

數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。數(shù)據(jù)結(jié)構(gòu)的基本操作：指對數(shù)據(jù)結(jié)構(gòu)的加工處理數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))：

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)：基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法)1.3數(shù)據(jù)結(jié)構(gòu)的分類及表示

某班學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號姓名專業(yè)政治面貌，表中的記錄是按學(xué)生的學(xué)號順序排列的。

學(xué)號姓名 專業(yè) 政治面藐

001 王洪 計(jì)算機(jī)黨員

002孫文計(jì)算機(jī)團(tuán)員

003 謝軍 計(jì)算機(jī)團(tuán)員

004 李輝 計(jì)算機(jī)團(tuán)員

005 沈祥福計(jì)算機(jī)黨員

006 余斌 計(jì)算機(jī)團(tuán)員

007 鞏力 計(jì)算機(jī)團(tuán)員

008 孔令輝計(jì)算機(jī)團(tuán)員學(xué)生基本情況登記表的圖示

001003002004006005008007學(xué)生間學(xué)號順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系例一常用的數(shù)據(jù)結(jié)構(gòu)

1）集合

2）線性結(jié)構(gòu)

3）樹結(jié)構(gòu)

4）圖結(jié)構(gòu)

5）其它復(fù)雜結(jié)構(gòu)

家族的族譜

假設(shè)某家族有10個(gè)成員A，B，C，D，E，F(xiàn)，G，H，I，J，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示例1.邏輯結(jié)構(gòu)圖1.5四類基本數(shù)據(jù)結(jié)構(gòu)示意

(1)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同屬于一個(gè)集合的關(guān)系外，無任何其它關(guān)系。

(2)線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對一的線性關(guān)系。

(3)樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。

(4)圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。邏輯結(jié)構(gòu)線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串、數(shù)組、廣義表非線性結(jié)構(gòu)——樹、圖

2.存儲結(jié)構(gòu)存儲結(jié)構(gòu)（又稱物理結(jié)構(gòu)）是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。形式化描述：D要存入機(jī)器中，建立一從D的數(shù)據(jù)元素到存儲空間M單元的映象S，D→M，即對于每一個(gè)d，d∈D,都有唯一的z∈M，使S（D）=Z,同時(shí)這個(gè)映象必須明顯或隱含地體現(xiàn)關(guān)系R。邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)的關(guān)系為：存儲結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身的映象。邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，兩者綜合起來建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。■順序映象（順序存儲結(jié)構(gòu)）

■非順序映象（非順序存儲結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算集合。按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)的存儲器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)的表示

圖示表示

圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；

001003002004006005008007學(xué)生基本情況表的圖示表示JIACBDHGFE家族樹的圖示表示1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示學(xué)生基本情況表的二元組表示（D，S）

二元組表示

二元組表示是用一個(gè)二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。D={001，002，003，004，005，006，007，008}S={R}R={<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}

家族樹的二元組表示（D，S）D={A，B，C，D，E，F(xiàn)，G，H，I，J}

S={R}

R={〈A,B>,<A,C>,<A,D>,<B,E>,<B,F>,<C,G>,<D,H>,<D,I>,<D,J>}1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示JIACBDHGFE

0010030020040060050080071．4算法與算法分析1.4算法與算法分析一算法的概念

算法是求解問題的操作序列

算法的基本特征：

1）輸入：0個(gè)或多個(gè)輸入；

2）輸出：1個(gè)或多個(gè)輸出；

3）有窮性：算法必須在有限步內(nèi)結(jié)束；

4）確定性：組成算法的操作必須清晰無二義性。

5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。

求兩個(gè)正整數(shù)m，n中的最大數(shù)MAX的算法（1）若m>n則max=m

（2）若m<=n則max=n例描述算法的書寫規(guī)則所有算法均以函數(shù)形式給出,算法的輸入數(shù)據(jù)來自參數(shù)表參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說明有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義,以及全局變量的說明等均在算法之前進(jìn)行說明評價(jià)算法標(biāo)準(zhǔn)

算法的正確性，可讀性，可維護(hù)性，健壯性等，1算法時(shí)間復(fù)雜度T（n）

本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。

1．4算法與算法分析O（n3）

稱為矩陣相乘算法時(shí)間復(fù)雜度；O（n3）表示矩陣相乘算法執(zhí)行時(shí)間與n3成正比,即O（n3）與n3同一數(shù)量級；n階矩陣相乘的算法For(i=1;i<=n;i++)

For(j=1;j<=n;j++){c[i][j]=0;

For(k=1;k<=n;k++)

c[i][j]+=a[i][k]*b[k][j]}

乘法加法執(zhí)行次數(shù)均為n3

例

矩陣相乘的基本運(yùn)算：乘法加法；

有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮

（1）算法平均時(shí)間復(fù)雜度

（2）算法在最壞情況下的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度

一般來說，設(shè)算法中基本操作的執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，算法的時(shí)間復(fù)雜度記作：

T(n)=O(f(n))

它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長率與f(n)的增長率相同。

1．4算法與算法分析算法的時(shí)間復(fù)雜度為O(N3)

1．4算法與算法分析

100元買100支筆,其中鋼筆3元/支,圓珠筆2元/支,鉛筆0.5元/支.寫算法輸出各種組合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)

printf