數據結構和算法簡介

數據結構：存儲和組織數據的方式，決定了數據的存儲方式和訪問方式。
算法：解決問題的思維、步驟和方法。
程序 = 數據結構 + 算法

算法

算法的獨立性

算法是獨立存在的一種解決問題的方法和思想，對于算法而言，實現的語言并不重要，重要的是思想，算法可以有不同的語言描述實現版本

算法的特點

• 有輸入：算法具有0個或者多個輸入
• 有輸出：算法至少有1個或者多個輸出
• 有窮性：算法在有限的步驟之后會自動結束而不會無限循環，并且每一個步驟可以在可接受的時間內完成
• 確定性：算法中的每一步都有確定的含義，不會出現二義性
• 可行性：算法的每一步都是可行的，即每一步都能夠執行有限的次數完成

算法對比

對于同一個問題，我們給出了兩種解決算法，在兩種算法的實現中，我們對程序的執行時間進行了測算，發現兩段程序執行的時間相差懸殊，由此我們可以得出結論：實現算法程序的執行時間可以反映出算法的效率
但是，單靠時間值衡量算法效率并不可靠

假設計算機執行算法每一個基本操作的時間是固定的一個時間單位，那么有多少個基本操作就代表花費多少時間單位，由此可以忽略機器環境的影響而客觀的反應算法的時間效率

$$.代碼執行總時間(T)=操作步驟數量?操作步驟執行時間$$

時間復雜度

時間復雜度表示一個蘇娜發隨著問題規模不斷變化的最主要趨勢，通常用來衡量一個算法的優劣

時間復雜度的表示形式

大O 記法 為算法的時間復雜度隨數據量變化的關系曲線，通常由最高次項決定，當數據量比較高時低次項的影響相對于高次項就很小，為了方便可以忽略

時間復雜度的計算規則

• 基本操作 時間復雜度為O(1)
• 順序結構 時間復雜度按加法計算
• 循環結構 時間復雜度按乘法計算
• 分支結構 時間復雜度取最大值
• 判斷一個算法的效率時，往往只需要關注操作數量的最高次項，其他次要項和常數項可以忽略
• 在沒有特殊說明時，我們所分析的算法的時間復雜度都是指最壞時間復雜度

最優最壞時間復雜度

分析算法時，存在集中可能的考慮

• 算法完成工作最少需要多少基本操作，即 最優時間復雜度
• 算法完成工作最多需要多少基本操作，即 最壞時間復雜度
• 算法完成工作平均需要多少基本操作，即 平均時間復雜度

最優最壞時間復雜度的作用

• 最優時間復雜度：反映的知識最樂觀最理想的情況，沒有參考價值
• 最壞時間復雜度：算法的一種保證，表示算法在此種程度的基本操作中一定能完成工作
• 平均時間復雜度：是對蘇娜發的一個全面評價，因此它完整全面的反映了這個算法的性質，但另一方面，這種平衡并沒有保證，不是每個計算都能在這個基本操作內完成。而且，對于平均情況的計算，也會因為應用蘇娜發的實例分布可能并不均勻而難以計算。

我們主要關注算法的最壞情況，即最壞時間復雜度

常見的時間復雜度

• $O(1)$ 常數階
• $O(logn)$ 對數階
• $O(n)$ 線數階
• $O(n^2)$ 平方階
• $O(n^3)$ 立方階

效率高到低分別是
$$O(1)>O(logn)>O(n)>O(n?logn)>O(n^2)>O(n^3)$$

空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的度量，類似于時間復雜度。一個算法的空間復雜度$S(n)$ 定義為該算法所耗費的存儲空間