《數(shù)據(jù)結(jié)構(gòu)》課件-第一章 緒論

數(shù)據(jù)結(jié)構(gòu)（Java語(yǔ)言描述）第1章緒論1.2數(shù)據(jù)結(jié)構(gòu)概述1.1 java簡(jiǎn)介1.3算法的描述和算法分析1.1Java簡(jiǎn)介1.1.1Java語(yǔ)言Java語(yǔ)言是一種高級(jí)語(yǔ)言，它具有以下性質(zhì)：面向?qū)ο?、多線程、與體系結(jié)構(gòu)無(wú)關(guān)、可解釋以及可移植。大多數(shù)語(yǔ)言要么用于編譯程序，要么用于解釋程序，這些程序經(jīng)翻譯后才能在計(jì)算機(jī)上運(yùn)行。Java語(yǔ)言的特殊之處在于用Java語(yǔ)言編寫(xiě)的程序既能被編譯又能被解釋。首先，使用編譯器將程序翻譯為一種被稱為Java字節(jié)碼的中間代碼，這是由Java平臺(tái)上的解釋器解釋的與平臺(tái)無(wú)關(guān)的代碼。然后，解釋器在計(jì)算機(jī)上分析并運(yùn)行每條Java字節(jié)碼。編譯只發(fā)生一次，而解釋在每次執(zhí)行程序時(shí)都發(fā)生。Java字節(jié)碼有助于使“一次編寫(xiě)，處處運(yùn)行”成為可能。1.1Java簡(jiǎn)介1.1.2Java虛擬機(jī)JVM（Javavirtualmachine）就是我們常說(shuō)的Java虛擬機(jī)，它是整個(gè)Java實(shí)現(xiàn)跨平臺(tái)的最核心的部分，所有的Java程序編譯后的類文件可以在虛擬機(jī)上執(zhí)行，并不直接與計(jì)算機(jī)的操作系統(tǒng)相對(duì)應(yīng)，而是經(jīng)過(guò)虛擬機(jī)間接與操作系統(tǒng)交互，由虛擬機(jī)將程序解釋給操作系統(tǒng)執(zhí)行。

JVM是Java平臺(tái)的基礎(chǔ)，和實(shí)際的計(jì)算機(jī)一樣，它也有自己的指令集，并且在運(yùn)行時(shí)操作不同的主存儲(chǔ)器（簡(jiǎn)稱內(nèi)存）區(qū)域。

JVM的主要工作是解釋自己的指令集到CPU的指令集或系統(tǒng)調(diào)用，保護(hù)用戶免被惡意程序騷擾。1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)中的一門(mén)專業(yè)基礎(chǔ)必修課，凡是設(shè)置計(jì)算機(jī)專業(yè)的院校都開(kāi)設(shè)了此課程。此外，一些常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)已經(jīng)滲透到計(jì)算機(jī)專業(yè)的各門(mén)課程中，例如《操作系統(tǒng)》課程中涉及到“隊(duì)列”和“樹(shù)”數(shù)據(jù)結(jié)構(gòu)的使用，即進(jìn)程調(diào)度的原則就是從就緒隊(duì)列中按照某種原則選取一個(gè)進(jìn)程執(zhí)行；在文件管理中，文件的一般都按照“樹(shù)”型結(jié)構(gòu)進(jìn)行存儲(chǔ)和處理。1.2數(shù)據(jù)結(jié)構(gòu)概述瑞士著名計(jì)算機(jī)科學(xué)家N.Wirth提出了著名公式“程序=算法+數(shù)據(jù)結(jié)構(gòu)”，表明了數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的重要地位。在計(jì)算機(jī)發(fā)展的初期，人們使用計(jì)算機(jī)的目的主要是處理數(shù)值計(jì)算問(wèn)題。由于當(dāng)時(shí)所涉及的運(yùn)算對(duì)象時(shí)簡(jiǎn)單的整型、實(shí)型或布爾類型數(shù)據(jù)，所以程序設(shè)計(jì)者的主要精力都集中在程序設(shè)計(jì)技巧上，而無(wú)需重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大以及軟硬件的發(fā)展，非數(shù)值計(jì)算問(wèn)題越來(lái)越顯得重要。這類問(wèn)題涉及到的數(shù)據(jù)結(jié)構(gòu)更為復(fù)雜，數(shù)據(jù)元素之間的相互關(guān)系一般無(wú)法用數(shù)學(xué)方程式直接描述。數(shù)學(xué)分析和計(jì)算方法在解決此類問(wèn)題時(shí)顯得力不從心，而設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)，才能有效地解決問(wèn)題。1.2數(shù)據(jù)結(jié)構(gòu)概述因此，掌握好數(shù)據(jù)結(jié)構(gòu)課程的知識(shí)，對(duì)于提高解決實(shí)際問(wèn)題的能力將會(huì)有很大的幫助。實(shí)際上，一個(gè)“好”的程序無(wú)非是選擇一個(gè)合理的數(shù)據(jù)結(jié)構(gòu)和好的算法，而好的算法的選擇很大程度上取決于描述實(shí)際問(wèn)題所采用的數(shù)據(jù)結(jié)構(gòu)。所以，要想編寫(xiě)出好的程序，僅僅學(xué)習(xí)計(jì)算機(jī)語(yǔ)言是不夠的，必須扎實(shí)的掌握數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)和基本技能。1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.2什么是數(shù)據(jù)結(jié)構(gòu)一般而言，利用計(jì)算機(jī)解決一個(gè)具體問(wèn)題時(shí)，大致需要經(jīng)過(guò)如下幾個(gè)步驟：（1）從具體問(wèn)題抽象出一個(gè)合適的數(shù)學(xué)模型；（2）設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法；（3）編寫(xiě)出程序，進(jìn)行測(cè)試、調(diào)整直到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問(wèn)題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。1.2數(shù)據(jù)結(jié)構(gòu)概述例1-1在八皇后問(wèn)題中，處理過(guò)程不是根據(jù)某種確定的計(jì)算法則，而是利用試探和回溯的探索技術(shù)求解。為了求得合理布局，在計(jì)算機(jī)中要存儲(chǔ)布局的當(dāng)前狀態(tài)。從最初的布局狀態(tài)開(kāi)始，一步步地進(jìn)行試探，每試探一步形成一個(gè)新的狀態(tài)，整個(gè)試探過(guò)程形成了一棵隱含的狀態(tài)樹(shù)。如圖1-1所示（為了描述方便，將八皇后問(wèn)題簡(jiǎn)化為四皇后問(wèn)題）?；厮莘ㄇ蠼膺^(guò)程實(shí)質(zhì)上就是一個(gè)遍歷狀態(tài)樹(shù)的過(guò)程。在這個(gè)問(wèn)題中所出現(xiàn)的樹(shù)也是一種數(shù)據(jù)結(jié)構(gòu)，它可以應(yīng)用在許多非數(shù)值計(jì)算的問(wèn)題。1.2數(shù)據(jù)結(jié)構(gòu)概述1.2數(shù)據(jù)結(jié)構(gòu)概述由以上例子可以看出，描述這類非數(shù)值計(jì)算問(wèn)題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而主要是線性表、樹(shù)、圖這類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說(shuō)數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及他們之間關(guān)系和操作的學(xué)科。1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.3基本概念和術(shù)語(yǔ)數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)中，它泛指所有能輸入計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)。它是計(jì)算機(jī)程序加工的原料，文字、表格、聲音、圖像等都稱為數(shù)據(jù)。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在程序中通常把數(shù)據(jù)元素作為一個(gè)整體進(jìn)行考慮和處理。例如，表1-1所示的學(xué)生表中，如果把每行當(dāng)作一個(gè)數(shù)據(jù)元素來(lái)處理，此表共包含7個(gè)數(shù)據(jù)元素。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成，例如表1-1中每一個(gè)學(xué)生的信息作為數(shù)據(jù)元素，而學(xué)生信息的每一項(xiàng)（如學(xué)號(hào)、姓名等）都是數(shù)據(jù)項(xiàng)。數(shù)據(jù)的最小單位即數(shù)據(jù)項(xiàng)。1.2數(shù)據(jù)結(jié)構(gòu)概述1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其之間的相互關(guān)系，可以看成相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。因此，可以把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括以下幾個(gè)方面。①數(shù)據(jù)元素之間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)。②數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)系統(tǒng)中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。③施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算。1.2數(shù)據(jù)結(jié)構(gòu)概述

1.2數(shù)據(jù)結(jié)構(gòu)概述數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)集合上的一組操作的總稱。例如，Java語(yǔ)言中的整型變量，其值集為某個(gè)區(qū)間上的整數(shù)，定義在其上的操作即為加、減、乘、除和模運(yùn)算等算術(shù)運(yùn)算。按“值”的不同特性，高級(jí)程序設(shè)計(jì)語(yǔ)言中的數(shù)據(jù)類型可分為兩類：原子類型和結(jié)構(gòu)類型。原子類型的值是不可分解的，例如Java語(yǔ)言中的基本類型（整型、布爾型等）。結(jié)構(gòu)類型的值是若干成分按照某種結(jié)構(gòu)組成的，因此是可以分解的，其組成成分既可以是結(jié)構(gòu)的，也可以是非結(jié)構(gòu)的。1.2數(shù)據(jù)結(jié)構(gòu)概述抽象數(shù)據(jù)類型是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)的存儲(chǔ)形式無(wú)關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響外部的使用。抽象數(shù)據(jù)類型定義格式如下：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：（數(shù)據(jù)對(duì)象定義） 數(shù)據(jù)關(guān)系：（數(shù)據(jù)關(guān)系定義） 數(shù)據(jù)操作：（數(shù)據(jù)操作定義）

}ADT抽象數(shù)據(jù)類型名1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)（1）集合集合是指數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。1.2數(shù)據(jù)結(jié)構(gòu)概述（2）線性結(jié)構(gòu)線性結(jié)構(gòu)是指該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)一的關(guān)系。其特點(diǎn)是開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是唯一的，除了開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外，其余結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)，有且僅有一個(gè)直接后繼。順序表就是一種典型的線性結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)概述（3）樹(shù)形結(jié)構(gòu)樹(shù)形結(jié)構(gòu)是指該結(jié)構(gòu)中結(jié)點(diǎn)之間存在一對(duì)多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)，但可以有多個(gè)直接后繼或終端結(jié)點(diǎn)。二叉樹(shù)就是一種典型的樹(shù)形結(jié)構(gòu)。1.2數(shù)據(jù)結(jié)構(gòu)概述（4）圖形結(jié)構(gòu)圖形結(jié)構(gòu)或稱為網(wǎng)狀結(jié)構(gòu)，是指該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在多對(duì)多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)的直接前驅(qū)和直接后繼的個(gè)數(shù)都可以是任意的。因此，圖形結(jié)構(gòu)可能沒(méi)有開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，也可能有多個(gè)開(kāi)始結(jié)點(diǎn)和多個(gè)終端結(jié)點(diǎn)。1.2數(shù)據(jù)結(jié)構(gòu)概述樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)統(tǒng)稱為非線性結(jié)構(gòu)，該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多或多對(duì)多的關(guān)系。由圖形結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和線性結(jié)構(gòu)的定義可知，線性結(jié)構(gòu)是樹(shù)形結(jié)構(gòu)的特殊情況，而樹(shù)形結(jié)構(gòu)又是圖形結(jié)構(gòu)的特殊情況。1.2數(shù)據(jù)結(jié)構(gòu)概述

1.2數(shù)據(jù)結(jié)構(gòu)概述

1.2數(shù)據(jù)結(jié)構(gòu)概述1.2.5數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)或在計(jì)算機(jī)中的表示（亦稱為映像），也就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式，它是依賴于計(jì)算機(jī)語(yǔ)言的。數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方式：順序映像和非順序映像。歸納起來(lái)，數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中有以下4種存儲(chǔ)結(jié)構(gòu)類型。1.2數(shù)據(jù)結(jié)構(gòu)概述（1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)，通常順序存儲(chǔ)結(jié)構(gòu)是借助于計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的數(shù)組來(lái)描述的。順序存儲(chǔ)方法的主要優(yōu)點(diǎn)是節(jié)省存儲(chǔ)空間，因?yàn)榉峙浣o數(shù)據(jù)的存儲(chǔ)單元全用戶存放結(jié)點(diǎn)的數(shù)據(jù)，結(jié)點(diǎn)之間的邏輯關(guān)系沒(méi)有占用額外的存儲(chǔ)空間。采用這種方法時(shí)，可實(shí)現(xiàn)對(duì)結(jié)點(diǎn)的隨機(jī)存取。然而順序存儲(chǔ)方法的主要缺點(diǎn)是不便于修改，對(duì)結(jié)點(diǎn)的插入、刪除運(yùn)算時(shí)，可能要移動(dòng)一系列的結(jié)點(diǎn)。1.2數(shù)據(jù)結(jié)構(gòu)概述（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的“指針”字段表示的。由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。鏈?zhǔn)酱鎯?chǔ)方法的優(yōu)點(diǎn)是便于修改，在進(jìn)行插入、刪除操作時(shí)，僅需要修改相應(yīng)結(jié)點(diǎn)的“指針域”，不必移動(dòng)結(jié)點(diǎn)。但與順序存儲(chǔ)方法相比，鏈?zhǔn)酱鎯?chǔ)方法的存儲(chǔ)空間利用率較低，因?yàn)榉峙浣o數(shù)據(jù)的存儲(chǔ)單元有一部分被用來(lái)存儲(chǔ)結(jié)點(diǎn)間的邏輯關(guān)系了。另外，由于邏輯上相鄰的結(jié)點(diǎn)在物理位置上并不一定相鄰，所以不能對(duì)結(jié)點(diǎn)進(jìn)行隨機(jī)方法操作。1.2數(shù)據(jù)結(jié)構(gòu)概述（3）索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)通常在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)還建立附加的索引表。索引表的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是:（關(guān)鍵字，地址），關(guān)鍵字唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)，地址作為指向結(jié)點(diǎn)的指針。這種帶有索引表的存儲(chǔ)結(jié)構(gòu)可以大大提高數(shù)據(jù)查找的速度。線性結(jié)構(gòu)采用索引存儲(chǔ)方法后，可以對(duì)結(jié)點(diǎn)進(jìn)行隨機(jī)訪問(wèn)。在進(jìn)行插入、刪除運(yùn)算時(shí)，只需移動(dòng)存儲(chǔ)在索引表中對(duì)應(yīng)結(jié)點(diǎn)的存儲(chǔ)地址，而不必移動(dòng)存放在結(jié)點(diǎn)表中結(jié)點(diǎn)的數(shù)據(jù)，所以仍保持較高的數(shù)據(jù)修改效率。索引存儲(chǔ)方法的缺點(diǎn)是增加了索引表，增加了存儲(chǔ)空間開(kāi)銷。1.2數(shù)據(jù)結(jié)構(gòu)概述（4）哈希存儲(chǔ)結(jié)構(gòu)哈希存儲(chǔ)結(jié)構(gòu)的基本思想是根據(jù)結(jié)點(diǎn)的關(guān)鍵字通過(guò)哈希函數(shù)直接計(jì)算出一個(gè)值，并將這個(gè)值作為該結(jié)點(diǎn)的存儲(chǔ)地址。哈希存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是查找速度快，只要給出待查找結(jié)點(diǎn)的關(guān)鍵字，就可以計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。與前3種存儲(chǔ)結(jié)構(gòu)不同的是，哈希存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的數(shù)據(jù)，不存儲(chǔ)結(jié)點(diǎn)之間的邏輯關(guān)系。哈希存儲(chǔ)結(jié)構(gòu)一般適用于要求對(duì)數(shù)據(jù)能夠進(jìn)行查找和插入的場(chǎng)合。1.3算法的描述和算法分析1.3.1算法的描述算法是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作；一個(gè)算法具有以下5個(gè)重要的特性：（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出1.3算法的描述和算法分析當(dāng)我們?cè)O(shè)計(jì)一個(gè)算法時(shí)，它應(yīng)該滿足以下幾條目標(biāo)：（1）正確性要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能和性能要求。這是最重要也是最基本的標(biāo)準(zhǔn)。（2）可讀性算法應(yīng)當(dāng)易于理解，也就是可讀性好。（3）健壯性算法要求具有良好的容錯(cuò)性，提供異常處理，能夠?qū)θ绾蔚妮斎脒M(jìn)行檢查。不經(jīng)常出現(xiàn)異常中斷或死機(jī)現(xiàn)象。（4）效率與低存儲(chǔ)量需求通常算法的效率主要指算法的執(zhí)行時(shí)間。對(duì)于同一個(gè)問(wèn)題，如果能有多種算法進(jìn)行求解，執(zhí)行時(shí)間短的算法效率高。算法存儲(chǔ)量指的是算法執(zhí)行過(guò)程中所需的大量存儲(chǔ)空間。1.3算法的描述和算法分析1.3.2影響算法效率的因素一個(gè)算法用高級(jí)語(yǔ)言實(shí)現(xiàn)以后，在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間與很多因素有關(guān)，主要因素列舉如下。①依據(jù)算法所選擇的具體策略；②問(wèn)題的規(guī)模，如求100以內(nèi)還是1000以內(nèi)的素?cái)?shù)；③編寫(xiě)程序的語(yǔ)言，對(duì)于同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率往往越低；④編譯程序所產(chǎn)生的計(jì)算機(jī)代碼的質(zhì)量；⑤計(jì)算機(jī)執(zhí)行指令的速度。1.3算法的描述和算法分析1.3.3算法效率的評(píng)價(jià)一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，算法的執(zhí)行時(shí)間取決于二者的綜合結(jié)果。為了便于比較同一問(wèn)題的不同算法，通常從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的原操作，算法執(zhí)行的時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)行次數(shù)（一條語(yǔ)句的運(yùn)行次數(shù)稱為語(yǔ)句頻度）的乘積。顯然，在一個(gè)算法中，執(zhí)行的基本運(yùn)算次數(shù)越少，其執(zhí)行時(shí)間就相對(duì)越少；執(zhí)行基本運(yùn)算的次數(shù)越多，其運(yùn)行時(shí)間也相對(duì)越多。也就是說(shuō)，一個(gè)算法的執(zhí)行時(shí)間可以看成基本運(yùn)算執(zhí)行的次數(shù)。1.3算法的描述和算法分析算法基本運(yùn)算次數(shù)T(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))記號(hào)“O”表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)和f(n)的增長(zhǎng)率相同，稱為算法的時(shí)間復(fù)雜度。“O”的形式定義為：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則T(n)=O(f(n))表示存在一個(gè)正的常數(shù)M，使得當(dāng)n≥n0時(shí)都滿足|T(n)|≤M|f(n)|，也就是只求出T(n)的最高階，忽略其低階項(xiàng)和常數(shù)，這樣既可以簡(jiǎn)化計(jì)算，又可以較為客觀地反映當(dāng)n很大時(shí)算法的效率。一個(gè)沒(méi)有循環(huán)的算法中基本運(yùn)算次數(shù)與問(wèn)題規(guī)模n無(wú)關(guān)，記為O(1)，也稱作常數(shù)階。一個(gè)只有一重循環(huán)的算法中基本次數(shù)與問(wèn)題規(guī)模n的增長(zhǎng)呈線性增大關(guān)系，記為O(n)，也稱線性階。1.3算法的描述和算法分析例如，以下3個(gè)程序段：

（a）{++x;s=0;}

（b）for(i=1;i<=n;i++){++x;s+=x;}

（c）for(j=1;j<=n;j++)

for(k=1;k<=n;k++){++x;s+=x;}

含基本操作“++x”的語(yǔ)句頻度分別為1、n和n2，則這3個(gè)程序段的時(shí)間復(fù)雜度分別為O(1)、O(n)和O(n2)，分別稱為常數(shù)階、線性階和平方階。各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在如下關(guān)系：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)

1.3算法的描述和算法分析例1-4分析以下算法的時(shí)間復(fù)雜度。voidfun(inta[],intn,intk){inti;i=0; //語(yǔ)句（1）while(i<n&&a[i]!=k) //語(yǔ)句（2） i++; //語(yǔ)句（3）return(i); //語(yǔ)句（4）}1.3算法的描述和算法分析

1.3算法的描述和算法分析例1-5分析以下算法的時(shí)間復(fù)雜度。floatRSum(floatlist[],intn)

{

count++;

if(n){

count++;

returnRSum(list,n-1)+list[n-1];

}

count++;

return0;

}

1.3算法的描述和算法分析

1.3算法的描述和算法分析這是一個(gè)遞推關(guān)系式，它可以通過(guò)轉(zhuǎn)換成如下公式來(lái)計(jì)算：根據(jù)上述結(jié)果可知，該程序的時(shí)間復(fù)雜度為線性階，即O(n)。

1.3算法的描述和算法分析1.3.4算法的存儲(chǔ)空間需求一個(gè)算法的空間復(fù)雜度是指算法運(yùn)行所需的存儲(chǔ)空間。算法運(yùn)行所需的存儲(chǔ)空間包括如下兩個(gè)部分。（1）固定空間需求這部分空間域所處理數(shù)據(jù)的規(guī)模大小和個(gè)數(shù)無(wú)關(guān)，也就是說(shuō)，與問(wèn)題實(shí)例的特征無(wú)關(guān)，主要包括程序代碼、常量、簡(jiǎn)單變量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。（2）可變空間需求這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關(guān)。例如，分別包含100個(gè)元素的兩個(gè)數(shù)組相加，與分別包含10個(gè)元素的兩個(gè)數(shù)組相加，所需的存儲(chǔ)空間顯然是不同的。這部分存儲(chǔ)空間包括數(shù)據(jù)元素所占的空間，以及算法執(zhí)行所需的額外空間，例如，運(yùn)行遞歸算法所需的系統(tǒng)?？臻g。1.3算法的描述和算法分析

1.3算法的描述和算