1.基本概念和術語數據

• 數據：是描述客觀事物的符號，計算機中可以操作的對象，是能被計算機識別，並輸入給計算機處理的符號集合
• 數據元素：是組成數據的、有一定意義的基本單位，在計算機中通常作為整體處理
• 數據項：一個數據元素可以由若幹個數據項組成 數據項是不可分割的最小單位
• 數據對象：是性質相同的數據元素的集合，是數據的子集
• 數據結構：是相互之間存在一種或多種特定關係的數據元素的集合

邏輯結構

是指數據對象中數據元素之間的相互關係

1. 集合機構：集合機構中的數據元素除了同屬於一個集合外，它們之間沒有其他關係
2. 線性結構：線性結構中的數據元素之間是一對一的關係
3. 樹形結構：樹形結構中的數據元素之間存在一種一對多的層次關係
4. 圖形結構：圖形結構的數據元素是多對多的關係

物理結構

存儲結構，是指數據的邏輯機構在計算機中的存儲形式

1. 順序存儲結構：把數據元素存放在地址連續的存儲單元裏。其數據間的邏輯關係和物理關係是一致的
2. 鏈式存儲結構：把數據元素存放在任意的存儲單元裏，這組存儲單元可以是連續的，也可以是不連續的

目的是將數據及邏輯關係存儲到計算機的內存中

抽象數據類型

是指一個數學模型及定義在該模型上的一組操作

體現了程序設計中問題分解、抽象和信息隱藏的特性

• 數據類型：是指一組性質相同的值的集合及定義在此集合上的一些操作的總稱

2.算法

算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，並且每條指令表示一個或多個操作

算法的特性

輸入、輸出、有窮性、 確定性 、可行性

要求

• 正確性：算法至少應該具有輸入、輸出和加工處理無歧義性、能正確反映問題的需求、能夠得到問題的正確答案。
• 可讀性：便於閱讀、理解和交流
• 健壯性：當輸入數據不合法時，算法也能做出相關處理，而不是產生異常或莫名其妙的結果
• 時間效率高和存儲量低

算法效率的度量方法

1. 事後統計方法：通過設計好的測試程序和數據，利用計算機計時器對不同算法編製的程序的運行時間進行比較，從而確定算法效率的高低
2. 事前分析估算方法：在計算機程序編製前，依據統計方法對算法進行估算。

算法時間複雜度

定義：表示隨問題規模n的增大，算法執行時間的增長率和f（n）的增長率相同，稱作算法的漸近時間複雜度

用大寫O( )來體現算法時間複雜度的記法，我們稱之為大O記法。

推到大O階的方法：通過觀察和計算，得出運算中的次數，是否有嵌套和循環，考察的是數列的能力

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n )<O(n!)<O(nn)

算法空間複雜度

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

本文到此結束，希望對大家有所幫助呢。