試談數據結構研究(doc 16頁)

試談數據結構研究內容提要：
鏈式結構的優缺點
鏈式存儲結構是采取連表指針來指示數據的存儲位置,這就可以是在內存中隨意的存儲,沒有必須連續儲存空間的要求,對於內存的要求相對教容易.但是要是是從小到大順序排列的數據,鏈式存儲結構的時間複雜度教小,效率高.但是要是不規則排布的數據一般時間複雜度較高,效率更低
算法漸進複雜度的表示方法
算法時間複雜度的漸進分析：在時間複雜度t(n)中，剔除不會從實質上改變函數數量級的項，經過這樣處理得到的函數是t(n)的近似效率值，但這個近似值與原函數已經足夠接近，當問題規模很大時尤其如此。這種效率的度量就稱為算法的漸進複雜度。(在不引起混淆的情況下，也可簡稱時間複雜度)
算法的最好、最壞和平均時間複雜度
算法的複雜度往往取決於輸入數據，例如一個排序算法的時間複雜度往往取決於輸入數據的原始有序程度。因此分析算法複雜度時往往要區分最好情況、最壞情況和平均情況。
例如，在一個包含n個元素的數組中查找某個數據(假定該數據是數組元素)：
最好情況：該數據就是第0個元素，隻需比較1次就可以結束了，其複雜度為O(1)。
最壞情況：該數據是數組最後一個元素，則需要比較n次，其複雜度為O(n) 。
評均情況：假設需要查找的數據是第0個元素、第1個元素、…、最後一個元素的概率相等，則平均需要查找的次數為：1×1/n + 2×1/n + … + n×1/n = (n+1)/2。其複雜度為O(n)。

..............................