[計算機軟件及應用]第1章緒論-資料下載頁
2025-01-19 17:34本頁面
【正文】 ) { change = FALSE。 // change 為元素進行交換標志 for (j=0。 ji。 ++j) if (a[j] a[j+1]) { a[j] ←→ a[j+1]。 change = TRUE 。} } // 一趟起泡 例三 起泡排序 62 四、算法的存儲空間需求 算法的 空間復雜度定義為 : 表示隨著問題規(guī)模 n 的增大 ,算法運行所需存儲量的增長率與 g(n) 的增長率相同。 S(n) = O(g(n)) 63 算法的存儲量 包括 : 1. 輸入數(shù)據 所占空間 2. 程序本身 所占空間 3. 輔助變量 所占空間 64 若 輸入數(shù)據 所占空間只取決于問題 本身， 和算法無關 ，則只需要分析 除 輸入和程序之外的 輔助變量 所占 額外 空間 。 若所需額外空間相對于輸入數(shù)據量 來說是常數(shù)，則稱此算法為 原地工作 。 若所需存儲量依賴于特定的輸入， 則通常按最壞情況考慮。 65 本章學習要點 66 1. 熟悉各名詞、術語的含義，掌握基本概念。 2. 理解算法五個特征的確切含義。 3. 掌握通過計算“原操作”語句的次數(shù)來估算算法時間復雜度的方法。 67 習題解答實例 68 ? 算法設計題 17 對于 一維數(shù)組 A[0..n1] (n1)， 設計在時間和空間方面盡可量有效率的算法 ， 將 A中的序列循環(huán)左移 p(0pn)個位置 ， 即將A中的數(shù)據從 （ A0, A1, ......, An1） 轉變成 （ Ap,Ap+1,...... ,An1,A0,A1,......,Ap1） ， 并分析所設計算法的時間復雜度和空間復雜度 。 69 從簡到繁，我們按四種思路構思算法，并逐一分析 時間和空間方面的效率。具體的算法參見習題的解答實例。 在下面的實例演示中，假設 n=12， p=3 70 （參考答案之 1） A0 A11 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 1 2 3 4 5 6 7 8 9 10 11 0 2 3 4 5 6 7 8 9 10 11 0 13 4 5 6 7 8 9 10 11 0 1 2 首先設計一個左移 1位的函數(shù)，然后 3次調用該函數(shù)，實現(xiàn)數(shù)組元素左移 3位。 71 （參考答案之 2） A0 A11 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 11 3 4 5 6 7 8 9 10 A0 A1 A2 先將 A0, A1, A2緩存到輔助空間，其余元素一次性左移 3位，再把緩存的那 3個元素復制到數(shù)組 A的尾部。 72 （參考答案之 3） A0 A11 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 3 6 9 0第一趟 A3 A11 A4 A2 A6 A7 A5 A9 A10 A8 A0 A1 第二趟 A3 A2 A4 A5 A6 A7 A8 A9 A10 A11 A0 A1 第三趟 每一趟，按步距 p=3, (循環(huán) )左移調換元素，一次定位，共進行 3趟。 73 （參考答案之 4） A0 A11 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 11 0 10 9 8 7 6 5 4 3 2 1 A3 A0 A4 A5 A6 A7 A8 A9 A10 A11 A2 A1 A3 A2 A4 A5 A6 A7 A8 A9 A10 A11 A0 A1 第一次逆置 第二次逆置 第三次逆置 通過三次逆置數(shù)組的元素來實現(xiàn)左移，首先，整體逆置；然后分別對左部的 9個元素和右部的 3個元素進行逆置。 74 四個算法的時空分析比較 ?參考答案之 1: 時間復雜度 O(p*n) 空 間復雜度 O(1) ?參考答案之 2: 時間復雜度 O(n) 空 間復雜度 O(p) ?參考答案之 3: 時間復雜度 O(n) 空 間復雜度 O(1) ?參考答案之 4: 時間復雜度 O(n) 空 間復雜度 O(1)
教學課件相關推薦
鄂ICP備17016276號-1