一个程式的空间复杂度是取决於执行程式所需的记忆体空间.pptVIP

Data Structure in C  ─ 演算法分析 大綱 基本概念 演算法 效率評估 效率分析 效率估計 基本概念 需求 所有大的程式都以一些定義專案目的規格書開始?會獲得輸入與輸出資訊 分析 可以由下而上分析或由上而下分析 設計 設計者從程式所需要的資料物件和資料的運算來設計系統 資料物件：可產生抽象資料型態 資料運算：需要演算法的規格並考量演算法的設計策略 抽象資料型態與演算法的規格是相互獨立的，我們可暫時不考慮實作的因素 基本概念 (續) 改良和編碼 在這個階段，我們為每一個資料物件選擇表示法，並編寫它的各種運算之演算法 驗證 這個階段包括程式正確性的驗證，以不同的輸入資料測試程式，並改正錯誤 演算法 定義：演算法(algorithms)是一組有限的指令，根據這些指令，可以完成一項特定的工作。此外，所有的演算法需符合下列的條件： 輸入：可以沒有或從外部提供多個資料 輸出：至少產生一個結果 明確的：每一個指令都很明白且沒有混淆不清 有限的：如果追蹤一個演算法指令，演算法會在有限的步驟之後停止 有效率的：每個運算即使都如“明確性的”定義，但仍是不夠的，演算法必須是一個可行的運算 定義：演算法是一個解決問題的有限步驟程序，也可以說是產生解答中一步一步的的程序 效率評估 對於一個程式而言，我們除了需要了解 是否符合原始規格 是否正確執行 是否有文件說明，以解釋如何使用與操作 是否有效率應用函數建立邏輯單元 是否易於閱讀 要考量程式能否有效率地使用記憶體 程式的執行時間是否可接受 效率評估 (續) 效率評估方法 效率分析(performance analysis) 著重於獲得和機器無關的估計時間和空間 以複雜度理論(complexity theory)為核心，又可分為空間複雜度(space complexity)與時間複雜度(time complexity) 效率估計(performance measurement) 利用獲得與機器相關的執行時間，以找尋出沒有效率的程式片段 效率分析 空間複雜度 一個程式的空間複雜度是取決於執行程式所需的記憶體空間 程式所需的空間為下列兩項的和 固定的空間需求 固定空間需求包括指令空間(用以儲存程式碼的空間)，用來存簡單變數，固定大小的結構變數和常數空間 可變的空間需求 包含了所有要解決問題中所有相關的結構化變數所需要的空間?還包含當函數採用遞迴方式呼叫時所需的空間?最常用的特性包括數量、大小及輸入與輸出值 效率分析 (續) 時間複雜度 一個程式的時間複雜度是取決於執行程式所需的計算時間 程式所需的時間為下列兩項的和 編譯時間 類似固定的空間項目。此外，一旦程式可以正確執行，我們可以多次執行而不必再從新編譯 執行時間 執行時間的估算並不十分容易，常見的有利用系統時間來計算程式時間或利用程式運算的次數來評量 時間複雜度較常為人們所使用 效率分析 (續) 程式的時間複雜度是以用來執行函數的程式所發生的步驟數目來表示 步驟數目是受測程式特性(輸入的數目、輸出的數目、輸入與值出之值等)的集合函數 使用者可依其想了解的部份，以步驟數目估算時間複雜度 Ex. 想知道當輸入資料量增加時，計算時間增加的程度為何？ Ex. 對不同的程式，我們想知道當輸入的值增大時，計算時間如何增加？ 效率分析 (續) 使用者必需先選擇相關的特性，以做為估算步驟的依據?步驟是與特性無關的計算單元 Ex.10個加法是一個步驟 Ex.100個加法也是一個步驟 在某些情況下單純只依特性來計算步驟數目並不一定準確 Ex.利用binary search找尋特定數字，而估算方式是依參數數目，但估算過程可能依數字所在的位置而有很大的差異，故步驟的估算會有很大的誤差。 三種步驟計數 最佳狀況：步驟計算是對指定的參數所執行的最少步驟數 最差狀況：步驟計算是對指定的參數所執行的最多步驟數 平均值：步驟計算是以指定的參數在實體上執行的平均步驟數 效率分析 (續) 步驟估算方式 Ex. 陣列元素相加乃將陣列中每一元素的值加總起來 int sum(int arr[], int n) { int i, total=0; for (i=0;in; i++) total+=arr[i]; return total; } 效率分析 (續) Ex. 陣列的相加表示將相對應的元素相加 void add(int a[][], int b[][], int c[][], int rows, int cols) { for (int i=0;irows; i++) for (int j=0;jcols;