緒論-算法【資料結構與算法】

    文章主要是對于

資料結構與算法課程學習的讀書記錄

。歡迎學習交流。

    [内容範圍]第一章緒論 -算法

文章目錄

• • 算法用途
  • 算法是滿足下列性質的指令序列
  • 計算機問題求解5步驟
  • 算法複雜度分析
  • 時間複雜度具體計算
  • 規定最壞、最好、平均時間複雜度目的
  • [回顧]算法複雜度分析流程圖
  • 漸進表達式的引入（替代計算步的準确計算）
  • 漸進分析的符号
• 總結

算法用途

設計并實作一種用計算機來解決問題的方法。

算法是滿足下列性質的指令序列

• 輸 入：有零個或多個外部量作為算法的輸入。
• 輸 出：算法産生至少一個量作為輸出。
• 确定性：組成算法的每條指令清晰、無歧義。
• 有限性：算法中每條指令的執行次數有限，執行每條指令的時間也有限。

計算機問題求解5步驟

• 問題的了解：清楚問題的輸入、要求和輸出；

• 資料結構設計：一方面要選擇或設計能有效表示和存儲應用問題中所涉及的資料

  對象的資料結構，同時還要選擇或設計能支援算法政策實作的資料結構；

• 算法設計：包括選擇算法政策、用适當的方式描述和逐漸細化算法步驟；

• 算法分析：發現有改進完善之處，傳回第二步，重新選擇或設計資料結構、重新

  設計算法；

• 程式實作：用某種計算機程式設計語言，定義資料結構、編寫實作算法的代碼

• 

算法複雜度分析

    算法複雜性是算法運作所需要的計算機資源的量，需要時間資源的量稱為時間複雜性，需要的空間資源的量稱為空間複雜性。

    這個量應該隻依賴于算法要解的問題的規模、算法的輸入和算法本身的函數。

    如果分别用N、I和A表示算法要解問題的規模、算法的輸入和算法本身，而且用C表示複雜性，那麼，應該有C=F(N,I,A)。一般把時間複雜性和空間複雜性分開，并分别用T和S來表示，則有： T=T(N,I)和S=S(N,I) 。

時間複雜度具體計算

由于空間複雜度很難去考慮，通常我們考慮了時間複雜度。公式如下：總而言之就是計算各個元運算的個數×各自的時間的一個彙總。

元運算就是語句（也叫做計算步），翻譯完就是不同語句的個數×各自執行的時間。

具體描述

例子如下

規定最壞、最好、平均時間複雜度目的

首先明确N是問題的規模，L是算法的輸入。分成三種情況是為了在算法時間複雜度的分析中，我們可以有三種結果（對應三種L）用于比較，避免了不同算法用不同的L産生不同的結果對我們分析對比好壞的影響。

問題的規模

算法的輸入

[回顧]算法複雜度分析流程圖

漸進表達式的引入（替代計算步的準确計算）

不難發現對于實際問題，有時候很難去比較時間複雜度，是以引入漸進表達。

漸進性态的表達

簡單例子如下

漸進分析的符号

記憶如下（重要）

總結

如果有錯誤可以評論私信。