數(shù)據(jù)結(jié)構(gòu)與算法-C++實(shí)現(xiàn)PPT第一章 緒論

數(shù)據(jù)結(jié)構(gòu)第一章緒論本章的內(nèi)容與目標(biāo)課程基本情況數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象與基本概念算法與算法分析課程基本情況學(xué)習(xí)目標(biāo)——學(xué)會(huì)編程掌握基本的數(shù)據(jù)結(jié)構(gòu)培養(yǎng)算法設(shè)計(jì)能力、程序設(shè)計(jì)能力

提問(wèn)：利用計(jì)算機(jī)求解問(wèn)題的實(shí)質(zhì)是什么？數(shù)據(jù)表示：將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中數(shù)據(jù)處理：處理數(shù)據(jù)，求解問(wèn)題培養(yǎng)算法分析和評(píng)價(jià)的能力評(píng)價(jià)算法、改進(jìn)算法學(xué)習(xí)難度——難課程基本情況能力培養(yǎng)理論課程工程知識(shí)：學(xué)習(xí)和運(yùn)用計(jì)算機(jī)科學(xué)知識(shí)和建模方法推演、分析實(shí)際工程問(wèn)題。問(wèn)題分析：認(rèn)識(shí)到計(jì)算機(jī)領(lǐng)域的工程問(wèn)題有多種解決方案可以選擇，并結(jié)合文獻(xiàn)查閱及研究，比較、尋求可替代的解決方案?，F(xiàn)代工具：了解計(jì)算機(jī)專業(yè)的主要算法和信息檢索工具的原理和方法，并理解其局限性。社會(huì)責(zé)任：能分析和評(píng)價(jià)計(jì)算機(jī)工程實(shí)踐和復(fù)雜工程問(wèn)題解決方案對(duì)社會(huì)、健康、安全、法律以及文化的影響，以及這些制約因素對(duì)項(xiàng)目實(shí)施的影響，并理解計(jì)算機(jī)專業(yè)工程實(shí)踐應(yīng)承擔(dān)的社會(huì)責(zé)任。課程基本情況能力培養(yǎng)課程設(shè)計(jì)問(wèn)題分析：能夠從工程科學(xué)的角度，結(jié)合文獻(xiàn)查閱及研究，對(duì)計(jì)算機(jī)領(lǐng)域復(fù)雜工程問(wèn)題的解決方案，分析影響因素，并獲得有效結(jié)論。環(huán)境可持續(xù)：知曉和理解環(huán)境保護(hù)和可持續(xù)發(fā)展的理念和內(nèi)涵，正確認(rèn)識(shí)計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展與環(huán)境和可持續(xù)發(fā)展的關(guān)系。個(gè)人與團(tuán)隊(duì)：理解個(gè)人在團(tuán)隊(duì)中的角色劃分，能夠組織、協(xié)調(diào)和指揮團(tuán)隊(duì)開(kāi)展工作。課程基本情況考核方式：平時(shí)30%，包括考勤(6分)、作業(yè)及實(shí)驗(yàn)(20分)和課堂參與(6分)考試70%，閉卷考試，難度不低于考研試題考試題型：以能力訓(xùn)練型題目為主實(shí)驗(yàn)必做題目：順序表、單鏈表、二叉樹(shù)、圖，隨課堂進(jìn)度完成考核標(biāo)準(zhǔn)：速度+完成質(zhì)量課程設(shè)計(jì)：分組，每組1題，課程設(shè)計(jì)周完成課程基本情況課程性質(zhì)數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)課程體系中最核心的課程之一承前啟后前導(dǎo)課：高等數(shù)學(xué)、程序設(shè)計(jì)語(yǔ)言、離散數(shù)學(xué)后續(xù)課：數(shù)據(jù)庫(kù)、操作系統(tǒng)……屬于武術(shù)中的“練功”科目學(xué)完C++以后，很多同學(xué)感覺(jué)“能考試，不能編程”“練武不練功，到頭一場(chǎng)空”“編程秘籍”就業(yè)、考研、職場(chǎng)生涯課程基本情況確保取得好成果的方法：請(qǐng)認(rèn)真上課，投入時(shí)間和注意力，認(rèn)真看書(shū)和課件把握上機(jī)實(shí)驗(yàn)的機(jī)會(huì)，認(rèn)真練習(xí)上機(jī)分組，自由組合，5-6人一組。通過(guò)同組討論的方法解決問(wèn)題認(rèn)真對(duì)待作業(yè)，嚴(yán)禁雷同

作業(yè)分兩類：個(gè)人完成的作業(yè)：每章交一次

1次啟發(fā)式作業(yè)：鼓勵(lì)組內(nèi)討論、自主完成實(shí)際動(dòng)手編程能力遠(yuǎn)比邏輯層面的理解要重要得多！??！課程基本情況C++編譯環(huán)境VC6.0，與新操作系統(tǒng)不兼容，在字符串等操作有缺陷visualstudio,容量大,對(duì)java支持不佳Codeblocks,推薦,小型編譯系統(tǒng),對(duì)java支持不佳Netneans(/downloads/),java環(huán)境，c++需配合cygwin(/)

eEclipse,

java環(huán)境，c++需配合mingw第一次課堂參與自學(xué)模板的內(nèi)容要求：下周三請(qǐng)一位同學(xué)主講，其他同學(xué)補(bǔ)充主講的同學(xué)要準(zhǔn)備PPT，其他同學(xué)可以不準(zhǔn)備要能讓同學(xué)們理解模板的用途、原理和使用方法請(qǐng)自薦或者推薦一位同學(xué)作為主講數(shù)據(jù)結(jié)構(gòu)的興起與發(fā)展數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人——DonaldKnuth

1938年出生，25歲獲得加州理工學(xué)院數(shù)學(xué)系博士學(xué)位。30歲任斯坦福大學(xué)計(jì)算機(jī)系教授。31歲，經(jīng)典巨著TheArtofComputerProgramming第一卷出版他計(jì)劃共寫7卷，到1973年第三卷出版時(shí)已經(jīng)震驚世界，36歲獲得圖靈獎(jiǎng)。之后致力于對(duì)排版技術(shù)進(jìn)行改造，結(jié)果就是對(duì)整個(gè)西文印刷行業(yè)帶來(lái)革命性變革的TEX排版和METAFONT字型設(shè)計(jì)系統(tǒng)2008年，第四卷《組合算法》出版“如果你認(rèn)為你是一名優(yōu)秀的程序員，就去讀第一卷，如果你可以讀懂整套書(shū)，請(qǐng)發(fā)一份簡(jiǎn)歷給我”——比爾蓋茨數(shù)據(jù)結(jié)構(gòu)的興起與發(fā)展數(shù)據(jù)結(jié)構(gòu)的發(fā)展階段無(wú)結(jié)構(gòu)階段結(jié)構(gòu)化階段：數(shù)據(jù)結(jié)構(gòu)＋算法＝程序面向?qū)ο箅A段：（數(shù)據(jù)結(jié)構(gòu)＋算法）＝程序……數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象計(jì)算機(jī)求解問(wèn)題的一般步驟？

問(wèn)題→想法→算法→程序→求模型的解待求解問(wèn)題的分類

數(shù)值問(wèn)題→數(shù)學(xué)方程

非數(shù)值問(wèn)題→數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象例1-1：用計(jì)算機(jī)來(lái)實(shí)現(xiàn)學(xué)籍管理—表序號(hào)姓名球隊(duì)狀態(tài)能力1喬幫主公牛正常1002閃電俠熱火傷病973魔術(shù)師湖人停賽99……………問(wèn)題：學(xué)籍管理中，對(duì)這張表進(jìn)行的運(yùn)算或處理有哪些？以你現(xiàn)在所學(xué)，如何在計(jì)算機(jī)中存儲(chǔ)一行元素？學(xué)號(hào)的作用是什么？數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象例1-2：人機(jī)對(duì)弈—樹(shù)結(jié)構(gòu)…………..……..………...……問(wèn)題1：樹(shù)結(jié)構(gòu)的元素關(guān)系與表結(jié)構(gòu)的元素關(guān)系有什么區(qū)別？問(wèn)題2：如何在計(jì)算機(jī)中存儲(chǔ)一個(gè)局面？數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象例1-3城市間交通網(wǎng)—圖問(wèn)題1：圖結(jié)構(gòu)的元素關(guān)系與樹(shù)結(jié)構(gòu)的元素關(guān)系有什么區(qū)別？

北京紐約巴黎倫敦東京墨西哥北京

10982124紐約109

55108巴黎82

397倫敦553

89東京10897

113墨西哥12489113

墨北紐倫東巴109108113821245597389問(wèn)題2:以你目前所學(xué)，如何在計(jì)算機(jī)里存儲(chǔ)一條邊？數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的定義

數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)集合數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理

例：學(xué)籍登記表中的一行，一個(gè)棋盤格局、一門課程數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位例：學(xué)生的學(xué)號(hào)、姓名等屬性數(shù)據(jù)對(duì)象：具有相同性質(zhì)的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)的基本概念例1-1：用計(jì)算機(jī)來(lái)實(shí)現(xiàn)學(xué)籍管理—表數(shù)據(jù)元素？數(shù)據(jù)項(xiàng)？數(shù)據(jù)對(duì)象？序號(hào)姓名球隊(duì)狀態(tài)能力1喬幫主公牛正常1002閃電俠熱火傷病973魔術(shù)師湖人停賽99……………數(shù)據(jù)結(jié)構(gòu)的基本概念例1-2：人機(jī)對(duì)弈—樹(shù)結(jié)構(gòu)…………..……..………...……數(shù)據(jù)元素？數(shù)據(jù)項(xiàng)？數(shù)據(jù)對(duì)象？數(shù)據(jù)結(jié)構(gòu)的基本概念例1-3城市間交通網(wǎng)—圖數(shù)據(jù)元素？數(shù)據(jù)項(xiàng)？數(shù)據(jù)對(duì)象？墨北紐倫東巴109108113821245597389數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)之間的關(guān)系包含關(guān)系：數(shù)據(jù)對(duì)象是由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項(xiàng)組成數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位，其中的數(shù)據(jù)項(xiàng)一般不予考慮。數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)：相互之間存在一定關(guān)系的數(shù)據(jù)元素的集合按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的整體存儲(chǔ)結(jié)構(gòu)：又稱為物理結(jié)構(gòu)，是數(shù)據(jù)及其邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)集合：數(shù)據(jù)元素之間的關(guān)系僅僅就是“屬于同一個(gè)集合”，沒(méi)有其他關(guān)系線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)一的線性關(guān)系數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的邏輯結(jié)構(gòu)樹(shù)結(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的層次關(guān)系圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在著多對(duì)多的任意關(guān)系數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示?！鹗嫉刂防?（,,）數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)：用一組連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲(chǔ)位置來(lái)表示。鏈接存儲(chǔ)結(jié)構(gòu)：用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來(lái)表示。0200020803000325…………例:（,,）02000325∧數(shù)據(jù)結(jié)構(gòu)的基本概念邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問(wèn)題的，反映了數(shù)據(jù)內(nèi)部的構(gòu)成方式；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。同種邏輯結(jié)構(gòu)的數(shù)據(jù)可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)；而采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率往往是不同的。數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口對(duì)數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)是指對(duì)數(shù)據(jù)的讀取、修改、加工、處理等操作。數(shù)據(jù)結(jié)構(gòu)的基本操作：各種應(yīng)用都能通過(guò)這些操作實(shí)現(xiàn)對(duì)數(shù)據(jù)結(jié)構(gòu)的各種訪問(wèn)。

訪問(wèn)接口：操作的調(diào)用形式與規(guī)范（例如形參表、返回類型等）。數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口：數(shù)據(jù)結(jié)構(gòu)基本操作接口的全體。數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型的概念數(shù)據(jù)類型（DataType）：一組值的集合以及定義于這個(gè)值集上的一組操作的總稱。例如：C++中的整型，實(shí)型變量抽象（Abstract）:抽出問(wèn)題本質(zhì)的特征而忽略非本質(zhì)的細(xì)節(jié)例如：地圖、汽車模型抽象數(shù)據(jù)類型（AbstractDataType，ADT）:一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在該結(jié)構(gòu)上的一組操作的總稱數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)DT是一種用戶定義的數(shù)據(jù)類型，其運(yùn)算指明了用戶如何對(duì)數(shù)據(jù)進(jìn)行操作C++語(yǔ)言使用類Class來(lái)表示抽象數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)ADT的基本思想數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)DT的一般形式數(shù)據(jù)結(jié)構(gòu)的基本概念A(yù)DT的例子ADT名：球星Data:描述數(shù)據(jù)的結(jié)構(gòu)姓名，年齡，球隊(duì)，各項(xiàng)能力，…Operation：描述數(shù)據(jù)的行為

操作1：構(gòu)造操作2：析構(gòu)操作3：踢球操作4：轉(zhuǎn)會(huì)操作5：受傷……EndADT算法與算法分析算法（Algorithm）:是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法的五大特性輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出?？尚行裕核惴枋龅牟僮骺梢酝ㄟ^(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。算法與算法分析算法評(píng)價(jià)——“好”算法的要求正確：對(duì)于合法的輸入，得到正確的結(jié)果魯棒性：算法的健壯程度。異常輸入情況下算法的表現(xiàn)簡(jiǎn)單性：算法容易理解和實(shí)現(xiàn)抽象分級(jí)：可讀性，便于理解。用模塊化方法實(shí)現(xiàn)算法高效性：盡可能減少算法的時(shí)間效率和空間效率算法與算法分析算法描述方法自然語(yǔ)言流程圖程序設(shè)計(jì)語(yǔ)言偽代碼UML例：需要在給定序列中查找指定元素key——折半查找算法算法與算法分析自然語(yǔ)言描述：粗線條地描述算法思想優(yōu)點(diǎn)：便于閱讀和理解缺點(diǎn)：冗長(zhǎng)、二義性注意事項(xiàng)：避免寫成自然段例：折半查找的自然語(yǔ)言描述Step1.用待查值key和序列的中間值m進(jìn)行比較，若想等，則查找成功Step2.如果待查值比中值大，則在中值的右半?yún)^(qū)繼續(xù)進(jìn)行折半查找Step3.否則在中值的左半?yún)^(qū)繼續(xù)進(jìn)行折半查找。算法與算法分析流程圖優(yōu)點(diǎn)：流程直觀缺點(diǎn)：嚴(yán)密性、靈活性不足；不適用于復(fù)雜算法算法與算法分析程序設(shè)計(jì)語(yǔ)言優(yōu)點(diǎn)：能由計(jì)算機(jī)執(zhí)行缺點(diǎn)：抽象性差，對(duì)語(yǔ)言能力要求高注意：將算法寫成子函數(shù)算法與算法分析偽代碼Pseudocode

介于自然語(yǔ)言和程序設(shè)計(jì)語(yǔ)言之間的方法，它采用某一程序設(shè)計(jì)語(yǔ)言的基本語(yǔ)法，操作指令可以結(jié)合自然語(yǔ)言來(lái)設(shè)計(jì)表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解，類似自然語(yǔ)言偽代碼并沒(méi)有嚴(yán)格的規(guī)則，常用“縮進(jìn)”表示分支結(jié)構(gòu)，常用連續(xù)的數(shù)字或字母來(lái)標(biāo)示同一即模塊中的連續(xù)語(yǔ)句算法與算法分析UML統(tǒng)一建模語(yǔ)言（UnifiedModelingLanguage）UML是描述、構(gòu)造和文檔化軟件系統(tǒng)的可視化語(yǔ)言。作用:建立軟件模型建模語(yǔ)言:提供交流的詞匯和規(guī)則可視化:通過(guò)標(biāo)準(zhǔn)圖符構(gòu)成圖形來(lái)描述模型通用標(biāo)準(zhǔn):成為軟件建模的標(biāo)準(zhǔn)語(yǔ)言,并且在其他領(lǐng)域也得到應(yīng)用。UML不屬于本課程范疇，本課程僅使用簡(jiǎn)單類圖和活動(dòng)圖UML的學(xué)習(xí)對(duì)于將來(lái)掌握軟件工程，向系統(tǒng)架構(gòu)師發(fā)展很有好處

算法與算法分析UML結(jié)構(gòu)UML構(gòu)造塊物件結(jié)構(gòu)物件行為物件分組物件注解物件關(guān)系關(guān)聯(lián)依賴泛化實(shí)現(xiàn)圖類圖順序圖對(duì)象圖協(xié)作圖構(gòu)件圖狀態(tài)圖部署圖活動(dòng)圖用例圖公共機(jī)制規(guī)格說(shuō)明修飾公共分類擴(kuò)展機(jī)制架構(gòu)用例視圖邏輯視圖進(jìn)程視圖實(shí)現(xiàn)視圖部署視圖算法與算法分析活動(dòng)圖的要素折半查找的活動(dòng)圖算法與算法分析算法分析的方法事后統(tǒng)計(jì)：將算法實(shí)現(xiàn)，測(cè)算其時(shí)間和空間開(kāi)銷。

缺點(diǎn)：⑴編寫程序?qū)崿F(xiàn)算法花費(fèi)較多的時(shí)間精力⑵測(cè)試結(jié)果依賴于計(jì)算機(jī)軟硬件等環(huán)境因素事前分析：對(duì)算法所消耗資源的一種估算方法算法分析（AlgorithmAnalysis）：對(duì)算法所需要的計(jì)算機(jī)資源——時(shí)間和空間進(jìn)行估算時(shí)間復(fù)雜度（TimeComplexity）空間復(fù)雜度（SpaceComplexity）算法與算法分析時(shí)間復(fù)雜度度量算法執(zhí)行的時(shí)間長(zhǎng)短，一般是問(wèn)題規(guī)模n的函數(shù)算法的執(zhí)行時(shí)間＝每條語(yǔ)句執(zhí)行時(shí)間之和執(zhí)行次數(shù)×執(zhí)行一次的時(shí)間

指令系統(tǒng)、編譯的代碼質(zhì)量因此，算法的時(shí)間復(fù)雜度是用基本語(yǔ)句的執(zhí)行次數(shù)來(lái)描述的,記作T(n)哪個(gè)因素是由算法決定的？執(zhí)行次數(shù)算法與算法分析例3：for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;例1：x++;例2：for(i=1;i<=n;i++)x++;如果程序由這三條語(yǔ)句組成，則總執(zhí)行次數(shù)為：T(n)=n2+n+1算法與算法分析漸進(jìn)復(fù)雜度估算：考慮影響算法效率的最主要的因素，忽略次要因素隨著n的增加，最主要影響算法效率的因素是算法與算法分析算法分析的標(biāo)記——大O符號(hào)當(dāng)問(wèn)題復(fù)雜度n增加時(shí)，運(yùn)算所需時(shí)間、空間代價(jià)T(n)的上界注意:來(lái)源于Orderof……里的O，絕對(duì)不是0定義：若存在兩個(gè)正常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))問(wèn)題的規(guī)模n：或大小。如：矩陣的階數(shù)、圖的結(jié)點(diǎn)個(gè)數(shù)、正整數(shù)個(gè)數(shù)……上述定義表明，如果對(duì)于足夠大的(大于某自然數(shù)n0)的n

，存在正數(shù)c，使T(n)不大于c×f(n)

，則T

是f的大O符號(hào)。算法與算法分析定義：若存在兩個(gè)正常數(shù)c和n0，對(duì)于任意n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))注意：1、對(duì)與同一對(duì)T(n)和f(n)，

c和n0通常有多個(gè)取值2、只說(shuō)明存在c和n0，但并不關(guān)心如何得到c和n0，也不關(guān)心如何在多組取值中選擇3、唯一關(guān)心的是：如何描述算法復(fù)雜程度的數(shù)量級(jí)別：最簡(jiǎn)形式的f(n)：?jiǎn)雾?xiàng)且無(wú)常數(shù)算法與算法分析復(fù)雜度分析中的簡(jiǎn)化原則

—專注引起復(fù)雜度變化的最顯著因素忽略常量

忽略所有復(fù)雜度屬于低數(shù)量級(jí)的項(xiàng)

算法與算法分析例：某算法執(zhí)行基本操作次，則略去常量忽略復(fù)雜度較低的項(xiàng)定理：若A(n)=amnm+am-1nm-1++a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)算法與算法分析算法分析算例，求下列算法的復(fù)雜度例1-5：++x;例1-6：for(i=0;i<n;i++)++x;基本語(yǔ)句：，執(zhí)行次數(shù)：基本語(yǔ)句：，執(zhí)行次數(shù)：例1-7：for(i=0;i<n;i++)for(j=0;j<n;j++)++x;基本語(yǔ)句：，執(zhí)行次數(shù)：算法與算法分析例1-8：for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];