資料結構與演算法
資料與資料之間的結構主要有三種：線性結構、樹結構、圖結構，這三個也是資料結構的基本結構
1、 線性結構：結構中的資料元素之間存在著一對一的線性關系。除第一個和最后一個資料元素外，每個資料元素只有一個前驅和一個后繼資料元素
2、 樹結構：結構中的資料元素之間存在著一對多的層次關系。除根節點外，每個資料元素只有一個前驅資料元素，可有0個或若干個后繼資料元素
3、 圖結構：結構中的資料元素之間存在著多對多的任意關系。每個資料元素可有0個或若干個前驅資料元素和0個或若干個后繼資料元素
運算集合（基本演算法）：討論資料結構的目的是為了在計算機中實作所需的操作施加于資料源數字上的一種操作，構成了資料的運算集合，所以運算集合是資料結構很重要的組成部分，
演算法的設計取決于資料的邏輯結構，演算法的實作取決于資料的物理存盤結構。
（一）演算法的概念和特性
演算法是對特定問題求解步驟的一種描述，它是指令的有限序列。做任何事情都必須事先想好進行的步驟，然后按部就班地進行，才不會發生錯誤，計算機解決問題也是如此。對于一些常用的演算法應該熟記，比如求階乘、求素數、求是否閏年等演算法，在解決實際問題時，可參考已有的類似演算法，按照業務邏輯設計出符合自己的演算法。
一個演算法應該具有以下五個重要特性。
⑴ 有窮性
一個演算法應包含有限個操作步驟。即一個演算法在執行若干個步驟之后應該能夠結束，而且每一步都在有限時間內完成。
⑵ 確定性
演算法中的每一步都必須有確切的含義，不能產生二義性。
⑶ 可行性
演算法中的每一個步驟都應該是能有效地執行，并得到確定的結果。
⑷ 輸入
所謂輸入，是指在演算法執行時，從外界取得必要的資料。計算機運行程式的目的是為了進行資料處理，在大多數情況下，這些資料需要通過輸入得到。有些情況下，資料已經包含在演算法中，演算法執行時不需要任何資料，所以一個演算法可以有零個或多個輸入。
⑸ 輸出
一個演算法有一個或多個輸出，這是演算法進行資料處理后的結果。沒有輸出的演算法是毫無意義的。
演算法的這些特性可以約束程式設計人員正確地書寫演算法，并使之能夠正確無誤地執行，達到求解問題的預期效果。
（二）演算法設計的要求
演算法設計的好壞關乎程式的執行效率，演算法的設計必須滿足下列四個要求。
⑴ 正確性
正確性的含義是演算法對于一切合法的輸入資料都能夠得出滿足要求的結果，事實上要驗證演算法的正確性是極為困難的，因為通常情況下合法的輸入資料量太大，用窮舉法逐一驗證是不現實的。所謂的演算法正確性是指演算法達到了測驗要求。
⑵ 可讀性
演算法的可讀性是指人對演算法閱讀理解的難易程度，可讀性高的演算法便于交流，有利于演算法的除錯和修改。通常增加演算法的可讀性是在書寫演算法時采用按縮進格式書寫、分模塊書寫等方法可增加演算法的可讀性。
⑶ 健壯性
對于非法的輸入資料，演算法能給出相應的回應，而不是產生不可預料的后果。
⑷ 效率與低存盤量需求
效率指的是演算法的執行時間。對于解決同一問題的多個演算法，執行時間短的演算法效率高。存盤量需求指演算法執行程序中所需要的最大存盤空間。存盤量需求越小的演算法效率越高。
（三）演算法的分析
解決一個問題可以有多種演算法，那么該怎樣判斷它們的優劣呢？判斷演算法優劣的標準很多，這里不做深入討論，但一個演算法除了正確性必須保證外，一個主要指標是它的效率。
⑴ 演算法效率的度量
演算法執行的時間是其對應的程式在計算機上運行所消耗的時間。程式在計算機上運行所需時間與下列因素有關：
① 演算法本身選用的策略；
② 書寫程式的語言；
③ 編譯產生的代碼質量；
④ 機器執行指令的速度；
⑤ 問題的規模。
第①條是演算法好壞的根本，第②③條要看具體的軟體支持，第④條要看硬體的性能。度量一個演算法的效率應拋開具體機器的軟、硬體環境，而書寫程式的語言、編譯產生的機器代碼質量、機器執行指令的速度都屬于軟硬體環境。所以拋開計算機軟硬體相關的因素，一個程式的運行時間，僅依賴于演算法的好壞和問題的規模。
對于一個特定演算法只考慮演算法本身的效率，而演算法自身的執行效率是問題規模的函式。對于同一個問題，選用不同的策略就對應不同的演算法，不同的演算法對應有各自的問題規模函式，根據這些函式就可以比較演算法的優劣。演算法的效率包括時間與空間兩個方面，分別稱為時間復雜度和空間復雜度。
⑵ 演算法的時間復雜度
一個演算法的執行時間大致上等于其所有陳述句執行時間的總和，對于陳述句的執行時間是指該條陳述句的執行次數和執行一次所需時間的乘積。陳述句執行一次實際所需的具體時間是與機器的速度、編譯程式質量、輸入資料等密切相關，與演算法設計的好壞無關。所以，可用演算法中陳述句的執行次數來度量一個演算法的效率。
首先定義演算法中一條陳述句的陳述句頻度，陳述句頻度是指陳述句在一個演算法中重復執行的次數。以下給出了兩個n×n階矩陣相乘演算法中的各條陳述句以及每條陳述句的陳述句頻度。
陳述句 陳述句頻度
for（i=0；i< n;i++） n＋1
for （j=0；j<n;j++） n2＋n
{
c[i][j]=0; n2
for (k=0;k< n; k++) n3＋n2
c[i][j]=c[i][j]+a[i][k]*b[k][j]; n3
}
演算法中所有陳述句的總執行次數為Tn=2n3+3n2+2n+1, 即陳述句總的執行次數是問題的規模n的函式f(n)（Tn= f(n)）。進一步地簡化，可用Tn運算式中n的最高次冪來度量演算法執行時間的數量級，即演算法的時間復雜度，記做：
T(n)=O(f(n))
上式是Tn= f(n)中忽略其系數的n的最高冪次項，它表示隨問題規模n的增大演算法的執行時間的增長率和f(n)的增長率相同，稱作演算法的漸進時間復雜度，簡稱時間復雜度。如上演算法的時間復雜度T(n)=O(n3)。
演算法中所有陳述句的總執行次數Tn是問題規模n的函式，即Tn= f(n)，其中 n的最高次冪項與演算法中稱作原操作的陳述句的陳述句頻度對應，原操作是演算法中實作基本運算的操作，在上面的演算法中的原操作是c[i][j]=c[i][j]+a[i][k]*b[k][j]。一般情況下原操作由最深層回圈內的陳述句實作。
T(n)隨n的增大而增大，增長得越慢，其演算法的時間復雜度越低。下列三個程式段中分別給出了原操作count++的三個不同數量級的時間復雜度。
① count++ ；
其時間復雜度為O(1)，稱之為常量階時間復雜度。
② for (i=1; i<= n; i++)
count++;
其時間復雜度為O(n)，是線性階時間復雜度。
③ for (i=1; i<= n; i++)
for(j=1;j<= n; j++)
count++;
其時間復雜度為O(n2)，平方階時間復雜度。
此外，演算法能呈現的時間復雜度還有：對數階O(log2n),指數階O(2n)等。
（3）演算法的空間復雜度
采用空間復雜度作為演算法所需存盤空間的量度，記作：
S(n)=O(f (n))
其中n為問題的規模。
程式執行時，除了需存盤本身所用的指令，常數，變數和輸入資料以外，還需要一些對資料進行操作的輔助存盤空間。
其中對于輸入資料所占的具體存盤量只取決于問題本身，與演算法無關，這樣只需要分析該演算法在實作時所需要的輔助空間單元數就可以了。
演算法的執行時間和存盤空間的耗費是一對矛盾體，即演算法執行的高效通常是以增加存盤空間為代價的，反之亦然。不過，就一般情況而言，常常以演算法執行時間做為演算法優劣的主要衡量指標。
以上部分內容源于老師所發檔案
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/54147.html
標籤：其他技術專區