數(shù)據(jù)結(jié)構(gòu)第二版(參考版)
2025-07-22 17:54本頁面
【正文】 ,n,x0和 n,輸出量為 pn(x0) 。 begin (1) if n=1 then (2) fac:=1 else (3) fac:=n*fac(n1) End。 作業(yè) 3 計算 n!的遞歸函數(shù) fac(n)如下，試分析它的 運行時間。 第一章 小結(jié) ? 數(shù)據(jù)結(jié)構(gòu)概念 ? 算法時間復(fù)雜度 作業(yè) 設(shè)有數(shù)據(jù)結(jié)構(gòu) (D,R),其中 D=(e1,e2,e3, E4,e5,e6,e7),R={r},r={(e1,e2),(e1,e7), (e2,e3),(e2,e4),(e3,e5),(e4,e5),(e2,e6), (e5,e6),(e6,e7)}.試按圖論中圖的畫法慣例畫出 該數(shù)據(jù)結(jié)構(gòu)圖。 C1和 C2為 計算機，且 C2的 計算速度是 C1的 10倍。 order(j,m)。 a[j]=temp。i++) if(a[i]a[j]) { temp=a[i]。 if(jm) { for(i=j+1。 ③ a:=s。i++) { s:=a+b。 ① for(i:=2。 ② 語句①頻度是 1，語句②頻度是 f(n),則有： 2f(n) ≤n f(n) ≤log2 n,取最大值 f(n)=log2n 該段程序的時間復(fù)雜度 T(n)=O(log2n) 算法及其評價 ? 例 計算下面程序的時間復(fù)雜度 : A:=0。 ② ] 其中語句 ①的頻度是 n1,語句②的頻度是 (n1)*(2n+1)= 2n2n1,則該 程序段的時間復(fù)雜度 T(n)=O(n2) 算法及其評價 ? 例 計算下面程序的時間復(fù)雜度 : i:=1。 算法描述和 算法分析 例 ： 程序段 語句頻度 時間復(fù)雜度 1. x:=x+1； 1 O(1) 常數(shù)階 2. FOR i:=1 TO n DO x:=x+1； n O(n) 線性階 3. FOR i:=1 TO n DO n FOR j:= 1 TO n DO x:=x+1； n^2 O(n2) 平方階 算法及其評價 ? 例 計算下面程序的時間復(fù)雜度： For i:=1 to (n1) do [ y:=y+1。 算法描述和 算法分析 ? 語句頻度 （ Frequency Count）： 語句可能重復(fù)執(zhí)行的最大次數(shù)。 ? 所有的算法均以過程或函數(shù)的形式表示； PROC 過程 名 (參數(shù) 表 )； ｛算法說明｝ 語句組 ENDP； {過程 名 } 算法描述 和算法分析 FUNC 函數(shù)名 (參數(shù) 表 )：類型； ｛函數(shù)說明｝ 語句組 RETURN(f) ENDF； {函數(shù)名 } 調(diào)用過程語句為：過程名（ 參數(shù) 表） 調(diào)用函數(shù)語句為：變量名：＝函數(shù)名（ 參數(shù) 表） 算法描述 和算法分析 ? 出錯語句： ERROR（ ‘出錯信息’）； ? 注釋語句：｛注釋內(nèi)容｝ ? 語句結(jié)束符號：； ? 語句組符號：［ ］ ? 基本函數(shù)： max()、 min()、 abs() 、 eof 、 eoln ? 布爾運算： AND、 OR、 NOT、 CAND、 COR 算法描述 和算法分析 ? 賦值語句：變量名：＝表達式； ? 分支語句： IF 條件 THEN 語句 ELSE 語句； CASE 條件１：語句１； ．．． 條件 n ： 語句 n； (ELSE 語句 n+1) ENDC； 算法描述 和算法分析 ? 循環(huán)語句： FOR 變量名：＝初值 TO 終值 DO 循環(huán)體； FOR 變量名：＝初值 DOWNTO 終值 DO 循環(huán)體； WHILE 條件 DO 循環(huán)體； REPEAT 循
公司管理相關(guān)推薦
鄂ICP備17016276號-1