【正文】
一、資料結構涵蓋的内容：
二、算法的基本概念：
1、算法的概念：
algorithm,是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或者多個操作。
2、算法的特性：
有窮性：指令序列是有限的
确定性：每條語句的含義明确，無二義性
可行性：每條語句都應在有限的時間内完成
輸入：零個或者多個輸入
輸出：一個或者多個輸出
3、算法與程式的差別：
程式：
（program）程式是軟體開發人員根據使用者需求開發的、用程式設計語言描述的适合計算機執行的指令（語句）序列。
程式包含的四個要素：
資料結構 算法 程式設計方法 程式設計語言
程式與算法不同。程式是算法用某種程式設計語言的具體實作。程式可以不滿足算法的有窮性，比如作業系統也是一種程式，如果你願意，你的電腦可以一直開着，保持作業系統的運作。
比如：
4、程式、算法、軟體之間的關系：
程式：算法的計算機實作。用某種程式設計語言實作。
算法：表示問題的解。
軟體：程式+文檔
如下圖所示：
程式設計＝資料結構＋算 法
三、資料類型：
1、資料類型：
是指一個值的集合和定義在集合上的操作集合。例如：java的整數類型(integer),就不僅僅表示整數數值的集合，還包括對整數類型進行的操作集合，加、減、乘、除、模等操作。
我們通常所指的資料類型是某種進階語言支援的基本資料類型。 比如java的基本資料類型：int、double、float、char等等。
java中的資料類型：
2、抽象資料類型：
一個數學模型以及定義在這個模型上的一組操作（由使用者定義，用以表示應用問題的資料模型）。
看起來抽象資料類型和資料類型的定義基本相同。不同點在于：資料類型通常是指某種進階語言的，而抽象資料類型使用者重新設計，一種概念。這裡的"抽象"的含義在于數學抽象。
原子類型：比如整型
固定聚合類型：比如複數，兩個實數确定的次序構成
可變聚合類型：比如汽車類型，構成的成分是不确定的。(因為小轎車、大卡車的構成是不同的)
抽象資料類型抽象的層次越高，那麼可複用性也越高。比如：java中的object是對所有對象的抽象，那麼就可以作為所有類的父類。
四、抽象資料類型的表示（代碼舉例）：
c語言使用結構體
java語言使用類
下面分别用c語言與java語言，來定義學醬油象資料類型。已知學生的資訊如下：
1、用c代碼定義一個學生類：
test1.c:
運作效果：
2、用java代碼定義一個學生類：
(1)student.java:
(2)javatest.java:（給學生類指派并列印出來）
運作效果如下：
五、算法的設計目标：
1、算法的設計目标：
（1）正确性：滿足具體問題的解，基本目标。
（2）可讀性：有利于人去了解算法。
（3）健壯性：輸入非法資料，能适當做出處理，不産生莫名其妙的輸出。
（4）高效性：包括時間的高效性（時間複雜度）和空間的高效性（空間複雜度）。
2、算法性能名額：
（1）算法的時間效率也稱為時間複雜度。
（2）算法的空間效率也稱為空間複雜度。
（3）同一問題可用不同算法解決，而一個算法的品質優劣将影響到算法乃至程式的效率。算法分析的目的在于選擇合适算法和改進算法。一個算法的評價主要從時間複雜度和空間複雜度來考慮。
（4）算法時間的高效性和空間的高效性通常是沖突的。所有一般隻會取一個平衡點。（這裡展現的是一種哲學思想，研究計算機，不就是研究時間和空間的概念嘛，魚與熊掌不可兼得哦）
（5）通常我們假設程式運作在記憶體中，且記憶體容量足夠使用，是以更多的是讨論時間複雜度。
六、算法的時間複雜度：
算法的時間複雜度反映了算法執行的時間長短。度量一個算法在計算機上執行的時間通常有兩種方式：
1.事後統計法：
2.事前分析法：(常用)
編寫算法使用的進階語言
程式設計産生的機器語言代碼品質
機器指令執行速度
問題規模
注：算法的時間複雜度是由最深層嵌套語句的頻度決定的。
2、o()函數：
表示算法的時間效率與算法所處理的資料元素個數n函數關系的最常用函數，即o()函數。
定義：
一般情況下，算法中基本操作重複執行的次數是問題規模n的某個函數，用t(n)表示，若有某個輔助函數f(n),使得當n趨近于無窮大時，t（n)/f(n)的極限值為不等于零的常數，則稱f(n)是t(n)的同數量級函數。記作t(n)=o(f(n)),稱o(f(n)) 為算法的漸進時間複雜度，簡稱時間複雜度。看下圖便知：
情況一：t(n)與問題規模n無關
當算法的時間複雜度t(n)與問題規模n無關時，此時算法的時間複雜度t(n)=o(1)。
情況二：t(n)與問題規模n有關
例1：設數組a和b在前面部分已經指派，求如下兩個n階矩陣相乘算法的時間複雜度：
上方代碼中：
例2：設n為如下算法處理的資料元素個數，求算法時間複雜度。代碼如下：
分析：
例3：分析冒泡排序算法的時間複雜度。代碼如下：
時間複雜度分析：
（1）最佳情況下，冒泡排序算法隻需要周遊一次就能确定數組已經排序好了，此時的時間複雜度為o(n)；
（2）最差情況下，需要進行n-1次周遊，則需進行n(n-1）/2次比較和記錄移動，此時冒泡排序算法的時間複雜度t(n)=o(n2)。
3、時間複雜度的大小關系：
以下六種計算算法時間的多項式是最常用的。其關系為：
指數時間的關系為：
當n取很大的值時，指數時間算法和多項式時間算法在所需時間上非常懸殊。
小知識：
np（nondeterministic polynomial）難問題：是指算法複雜度難以用多項式表示的問題，算法複雜度通常是n的指數級，正常算法很難求解。
七、算法的空間複雜度：
空間複雜度是指算法在運作期間所需要的記憶體空間的數量級。記作：s(n)=o(f(n))，其中n為問題的規模(或大小)。
注：由于大部分算法的空間複雜度問題并不嚴重，并且算法的空間複雜度分析方法和算法的時間複雜度分析方法基本相同，是以一般資料結構隻讨論算法的時間複雜度，不讨論算法的空間複雜度。
代碼舉例：分析如下算法的空間複雜度
上方代碼中，當程式調用reserse(a,b)函數時，要配置設定的記憶體空間包括：引用a,引用b,局部變量n和局部變量i；
是以f(n)=c;其中c為常量。是以該算法的空間複雜度s(n)=o(1)。
八、總結：
算法的時間複雜度和兩個因素有關：算法中的最大嵌套循環層數；最大嵌套循環結構中每次循環的次數。
一般來說，具有多項式時間複雜度的算法是可以接受的；具有指數（不是對數）時間複雜度的算法，隻有當n足夠小時才可以使用。一般效率較好的算法要控制在o(n)或者o(log2 n)