文章主要是對于
資料結構與演算法課程學習的讀書記錄，歡迎學習交流，[內容范圍]第一章緒論 -演算法
文章目錄
- 演算法用途
- 演算法是滿足下列性質的指令序列
- 計算機問題求解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產生不同的結果對我們分析對比好壞的影響，
問題的規模
演算法的輸入
[回顧]演算法復雜度分析流程圖
漸進運算式的引入（替代計算步的準確計算）
不難發現對于實際問題，有時候很難去比較時間復雜度，所以引入漸進表達，
漸進性態的表達
簡單例子如下
漸進分析的符號
記憶如下（重要）
總結
如果有錯誤可以評論私信，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/260357.html
標籤：AI
上一篇：【VideoQA最新論文閱讀】第一篇視頻問答綜述Video Question Answering: a Survey of Models and Datasets