Linux環境程式設計之檔案I/O(七)：目錄檔案及操作

什麼是資料結構？

資料結構是互相之間存在一種或多種特定關系的資料元素的集合。

還有一些概念（資料、資料元素、資料項、資料對象、資料類型...）

傳統上，我們把資料結構分為邏輯結構和實體結構。

邏輯結構：是指資料對象中資料元素之間的互相關系，也是我們今後最需要關注和讨論的問題。

實體結構：是指資料的邏輯結構在計算機中的存儲形式。

邏輯結構分為以下四種：

1.集合：集合結構中的資料元素除了同屬于一個集合外，之間沒有任何關系。

2.線性結構：元素之間一對一。

3.樹形結構：一對多。

4.圖形結構：多對多。

實體結構分為以下兩種：

1.順序存儲結構：資料元素存放在位址連續的存儲單元裡，其資料間的邏輯關系與實體關系一緻。

2.鍊式存儲結構：資料元素放在任意的存儲單元裡，可以連續也可以不連續。

談談算法

程式=資料結構+算法

算法的五個基本特征：輸入、輸出、有窮性、确定性和可行性。

<1>算法具有零個或多個輸入。

<2>算法至少有一個或多個輸出。

<3>指算法在執行有限的步驟之後，自動結束而不會出現無限循環，并且每一個步驟在可接受的時間内完成。

<4>算法的每一個步驟都具有确定的含義，不會出現二義性。

<5>算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限次數完成。

設計要求：

<1>正确性

<2>可讀性

<3>健壯性

<4>時間效率高

<5>存儲量低。

是以在度量過程中産生了兩個複雜度，分别為時間複雜度和空間複雜度。

時間複雜度

算法時間複雜度的定義：在進行算法分析時，語句總的執行次數T(n)是關于問題規模n的函數，進而分析T(n)随n的變化情況并确定T(n)的數量級。

算法的時間複雜度，也就是算法的時間量度，記作：T(n)= O(f(n))。

它表示随問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。

一般情況下，随着輸入規模n的增大，T(n)增長最慢的算法為最優算法。

計算方法：

<1>用常數1取代運作時間中的所有加法常數。

<2>在修改後的運作次數函數中，隻保留最高階項。

<3>如果最高階項存在且不是1，則去除與這個項相乘的常數,得到的最後結果就是大O階。

舉例：

(1)

純加法常數 執行時間為1+1+1 是以時間複雜度記為O(1)

(2)

執行時間為 O(1) + O(n) //for會循環執行n次是以時間複雜度為O(n)  

(3)

外層執行O(n)次，内層執行O(n)因為時間複雜度為O(n^2) 

(4)

由于當i=0時，内循環執行了n次，當i=1時，内循環則執行n-1次……

當i=n-1時，内循環執行1次，是以總的執行次數應該是：n+(n-1)+(n-2)+…+1 = n(n+1)/2

取最高次幂是以時間複雜度為O(n^2) 

(5)

由于每次i*2之後，就舉例n更近一步，假設有x個2相乘後大于或等于n，則會退出循環。

于是由2^x = n得到x = log(2)n，是以這個循環的時間複雜度為O(logn)。

最壞情況與平均情況

我們查找一個有n個随機數字數組中的某個數字，最好的情況是第一個數字就是，

那麼算法的時間複雜度為O(1)，但也有可能這個數字就在最後一個位置，那麼時間複雜度為O(n)。

平均運作時間是期望的運作時間，最壞運作時間是一種保證。

在應用中，這是一種最重要的需求，通常除非特别指定，我們提到的運作時間都是最壞情況的運作時間。

空間複雜度

算法的空間複雜度通知計算方法所需的存儲空間實作，算法的空間複雜度的計算公式記作:S(n)=O(f(n))其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。 

參考<<大話資料結構>>