數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第1章(參考版)
2024-08-16 07:41本頁面
【正文】 算法的時間復(fù)雜度僅與問題的規(guī)模相關(guān)嗎 ? 按增長率由小至大的順序排列下列各函數(shù)： 2^100, (2/3)^n， (3/2)^n， n^n , , n! ， 2^n ， lgn ,n^lgn, n^(3/2) 2022年 9月 5日星期三 第 77頁 重慶工商大學(xué) 計算機(jī)與信息工程學(xué)院 。y。 y=100。 else i++。 // n1 while(i+j=n) while (x=(y+1)*(y+1)) {if (ij)j++。 j=0。 } while(in)。} k=k+10*i。 while(in) do{ { k=k+10*i。 k=0 (2) i=0。 常用的存儲表示方法有哪幾種 ? 設(shè)三個函數(shù) f,g,h分別為 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^+5000nlgn 請判斷下列關(guān)系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^) (4) h(n)=O(nlgn) 2022年 9月 5日星期三 第 75頁 設(shè)有兩個算法在同一機(jī)器上運(yùn)行 ， 其執(zhí)行時間分別為100n^2和 2^n,要使前者快于后者 ， n至少要多大 ? 設(shè) n為正整數(shù)，利用大 O記號，將下列程序段的執(zhí)行時間表示為 n的函數(shù)。 2022年 9月 5日星期三 第 74頁 作業(yè) : 簡述下列概念：數(shù)據(jù) 、 數(shù)據(jù)元素 、 數(shù)據(jù)類型 、 數(shù)據(jù)結(jié)構(gòu) 、邏輯結(jié)構(gòu) 、 存儲結(jié)構(gòu) 、 線性結(jié)構(gòu) 、 非線性結(jié)構(gòu) 。 算法的時間復(fù)雜度是比較不同算法效率的一種準(zhǔn)則，算法時間復(fù)雜度的估算基于算法中基本操作的重復(fù)執(zhí)行次數(shù)，或處于最深層循環(huán)內(nèi)的語句的頻度。一個完整的算法應(yīng)該具有下列五個要素：有窮性、確定性、可行性、有輸入和有輸出。抽象數(shù)據(jù)類型的三大要素為數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本操作，同時數(shù)據(jù)抽象和數(shù)據(jù)封裝是抽象數(shù)據(jù)類型的兩個重要特性 2022年 9月 5日星期三 第 72頁 ? 算法是進(jìn)行程序設(shè)計的另一不可缺少的要素。 數(shù)據(jù)結(jié)構(gòu)的操作是和數(shù)據(jù)結(jié)構(gòu)本身密不可分的，兩者作為一個整體可用抽象數(shù)據(jù)類型進(jìn)行描述。由關(guān)系不同可將數(shù)據(jù)結(jié)構(gòu)分為四類：線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)和集合結(jié)構(gòu)。數(shù)據(jù)元素可以是不可分割的原子，也可以由若干數(shù)據(jù)項合成，因此在數(shù)據(jù)結(jié)構(gòu)中討論的基本單位是數(shù)據(jù)元素，而最小單位是數(shù)據(jù)項。 2022年 9月 5日星期三 第 69頁 本章是為以后各章討論的內(nèi)容作基本知識的準(zhǔn)備，介紹數(shù)據(jù)結(jié)構(gòu)和算法等基本概念。 若所需額外空間相對于輸入數(shù)據(jù)量 來說是常數(shù)，則稱此算法為 原地工作 。} } // 一趟起泡 2022年 9月 5日星期三 第 66頁 四、算法的存儲空間需求 算法的 空間復(fù)雜度定義為 : 表示隨著問題規(guī)模 n 的增大， 算法運(yùn)行所需存儲量的增長率 與 g(n) 的增長率相同。 ++j) if (a[j] a[j+1]) { a[j] ←→ a[j+1]。 // change 為元素進(jìn)行交換標(biāo)志 for (j=0。 change。 i1 amp。 a[], int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。 i n1。 ++k ) if (a[k] a[j] ) j = k。 // 選擇第 i 個最小元素 for ( k = i+1。 a[], int n) { // 將 a 中整數(shù)序列重新排列成自小至大有序的整數(shù)序列 。 ++k) c[i,j] += a[i,k]*b[k,j]。 for (k=1。 j=n。 i=n。 2022年 9月 5日星期三 第 63頁 例 一 兩 個 矩 陣 相 乘 void mult(int a[], int b[], intamp。 2022年 9月 5日星期三 第 59頁 假如，隨著問題規(guī)模 n 的增長，算法執(zhí)行時間的增長率和 f(n) 的增長率相同 ，則可記作： T (n) = O(f(n)) 稱 T (n) 為算法的 (漸近 )時間復(fù)雜度。 2022年 9月 5日星期三 第 55頁 4． 高效率與低存儲量需求 通常，效率指的是 算法執(zhí)行時間 ； 存儲量指的是算法執(zhí)行過程中 所需的 最大存儲空間 ，兩者都與問題的規(guī)模 有關(guān)。 解決可讀性的方法： ,層次分明 2022年 9月 5日星期三 第 54頁 3． 健壯性 當(dāng) 輸入的數(shù)據(jù) 非法 時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴?進(jìn)行相應(yīng)處理 ，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。 其次， 對算法是否 “ 正確 ” 的 理解可以有以下 四個層次 ： a． 程序中不含語法錯誤； b． 程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 2022年 9月 5日星期三 第 52頁 c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果； 通常以 第 c 層 意
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1