一、緒論
-
程式設計 = 資料結構 + 演算法
-
資料結構 → 資料元素相互之間存在的一種或多種特定關系的集合
-
資料結構分為邏輯結構和物理結構
- 邏輯結構：資料物件元素之間的相互關系
- 物理結構：資料的邏輯結構在計算機中的存盤形式
四大邏輯結構
- 集合結構：集合結構中的資料元素除了同屬于一個集合外，它們之間沒有其他任何關系（集合）
- 線性結構：資料元素之間是一對一的關系（鏈表）
- 樹形結構：元素之間存在一種一對多的層次關系（樹）
- 圖形結構：資料元素之間是多對多的關系（圖）
* 物理結構
- 根據物理結構定義，可知物理結構研究的其實是如何把資料元素存盤到計算機的存盤器中
- 資料元素的存盤結構形式有兩種：順序存盤和鏈式存盤
- 順序結構：將資料元素存放在地址
連續的存盤單元里，其資料間的邏輯關系和物理關系是一致的（陣列結構） - 鏈式結構：
- 把資料元素存放在任意的存盤單元里，這組存盤單元可以是連續的，也可以是不連續的，
- 鏈式結構的資料元素存盤關系并不能反映其邏輯關系，因此需要用一個指標存放資料元素的地址，這樣子通過地址就可以找到相關聯資料元素的位置
- 順序結構：將資料元素存放在地址
二、演算法
-
演算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條指令表示一個或多個操作
-
五個特征：輸入、輸出、有窮性、確定性、可行性
- 輸入：演算法具有零個或多個輸入（引數）
- 輸出：演算法至少有一個或多個輸出
- 有窮性：演算法在執行一定得到步驟之后，自動結束而不會出現無限回圈，并且每一個步驟在可接受的時間內完成
- 確定性：
- 演算法的每一個步驟都具有確定的含義，不會出現二義性
- 演算法在一定條件下，只有一條執行路徑，相同的輸入只能有唯一的輸出結果
- 演算法的每一個步驟都應該被精確定義而無歧義
- 可行性：演算法的每一步都能夠通過執行有限次數完成
-
演算法的設計要求
-
正確性
- 演算法至少應該具備輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案
- 可分為四個四個層次
- 1、演算法程式沒有語法錯誤
- 2、對于合法的輸入能夠產生滿足要求的輸出
- 3、對于非法的輸入能夠產生滿足規格的說明
- 4、演算法程式對于故意刁難的測驗輸入都有滿足要求的輸出結果
-
可讀性
- 方便閱讀、理解、交流、以及他人修改
-
健壯性
- 當輸入資料不合法時，演算法也能夠做出相關處理，而不是產生例外、崩潰或莫名其妙的結果
-
時間效率高和存盤量低
-
三、時間復雜度和空間復雜度
演算法效率的度量方法
-
事后統計法，利用時間計時器，缺陷較大
-
事前分析估演算法：在計算機程式撰寫前，依據統計方法對演算法進行估算
-
拋開計算機硬體、軟體有關的因素，一個程式的運行時間依賴于演算法的好壞和問題的輸入規模(輸入量的多少)
-
研究演算法的復雜度，側重研究的是輸入規模擴大增長量的一個抽象，并非精確到執行多少次；
-
不計回圈索引的遞增或回圈終止條件、變數宣告、列印結果等操作；最重要的是把程式看成是獨立于程式設計語言的演算法或一系列步驟
-
基本運算元量<=關聯=>輸入模式
-
函式的漸近增長
- 函式的漸近增長：給定兩個函式f(n)和g(n),如果存在一個整數N，使得對于所有的n>N，f(n)總是大于g(n)，那么，我們說f(n)的增長漸近快于g(n)；
- 隨著規模增大時，函式中的常數和其他次要項常常可以忽略，而應關注最高項的階數
演算法的時間復雜度
-
定義：語法總的執行次數T(n)是關于問題規模n的函式，進而分析T(n)隨n的變化情況并確定T(n)的數量級，演算法的時間復雜度，也就是演算法的時間量度，記作:T(n) = O(f(n))，它表示隨問題規模n的增大，演算法執行時間的增長率和f(n)的增長率相同，稱作演算法的漸近時間復雜度，簡稱時間復雜度，f(n)是問題規模n的某個函式，==>（執行次數 == 時間）
-
隨著輸入規模n的增大，T(n)增長最慢的演算法為最優演算法，
-
推導大O階方法：
- 用常數1取代運行時間中的所有加法常數，
- 在修改后的運行次數函式中，只保留最高階項，
- 如果最高階項存在且不是1，則去除與這個項相乘的常數(如：3n^2 --> n^2)，
- 常數階、線性階、平方階、次方階、對數階、nlogn階、指數階…
- 從小到大:O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
-
函式呼叫的時間復雜度
//例子
int i, j;
for (i = 0; i < n; i++){
function(i);
}
void function(int count){
int j;
for (j = count; j < n; j++){
printf( "%d", j);
}
}
函式內部回圈次數–外部回圈次數，n + (n-1) + (n-2) +…+ 1 = (n+1)n/2 ==>時間復雜度：O(n^2)
-
最壞情況與平均情況
- 最壞運行時間是一種保證，這是一種最重要的需求；通常除法特別指定，一般提到的運行時間都是最壞情況的運行時間
- 平均運行時間是期望的運行時間
-
演算法的空間復雜度
- 計算演算法所需的存盤空間實作，演算法的空間復雜度的計算公式為：s(n) = 0(f(n))，其中n為問題規模，f(n)為陳述句關于所占存盤空間的函式，
-
通常，“時間復雜度”來指運行時間的需求，用“空間復雜度”指空間的需求，復雜度通常指時間復雜度
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/290877.html
標籤：其他
下一篇：Linux云計算 --中國三大電商大廠都在使用的《 GitLab與Jenkins結合構建持續集成(CI)環境》是如何排列