1.1 計算機問題求解
一般而言，人們需要的不是解決一個具體問題的程序，而是解決一類問題的程序。
對于求平方根這樣的簡單問題，人們希望的也不是專用于求某個數(例如2)的平方根的函數，而是能求任何數的平方根的函數。
用計算機解決問題的過程分為兩個階段:
? ? ? ? 1、程序開發者針對要解決的問題開發出相應的程序； ---- 程序設計
? ? ? ? 2、使用者運行程序處理問題的具體實例，完成具體計算。 ---- 功能使用
1.1.1 程序開發過程
1、需求分析階段---模糊需求細化
2、設計階段---嚴格描述求解過程
3、編碼階段 -- 使用編程語言寫代碼實現
4、檢查測試階段 --- 檢查語法錯誤，修正邏輯錯誤
1.3、算法和算法分析
1.3.1、問題、問題實例和算法
算法性質：有窮性、可行性、確定性、終止性、輸入/輸出。
算法描述：問題解決的辦法，要方便人們的閱讀和使用。常見的算法：枚舉法、貪心法、分治法、回溯法、動態規劃、分值限界法等。
程序：算法的實現，算法的落地。
算法設計模式：是人們對經驗的總結，只能借鑒，不應作為教條。這些模式并不相互隔絕也不互相排斥。例如，一般而言復雜的問題都需要分解;而最簡單的情況經常可能采用枚舉和判斷的方式處理。
1.3.2、算法的代價及其度量
?
在研究現實世界中的計算問題時，必須考慮計算的代價。該算法:在求解過程中需要多少存儲空間?完成問題實例的求解需要多長時間?
同一個算法能應用于不同的實例，計算的實際代價通常與實例的規模(大小)有關。3000X3000的矩陣計算自然要比3X3的矩陣計算花費更多的時間和空間。因此，可以把一個算法的計算(時間和空間)開銷定義為問題的實例規模的函數。
算法分析就是針對一個具體算法，設法確定一種函數關系，以問題實例的某種規模n為參量，反映出這個算法在處理規模n的問題實例時需要付出的時間(或者空間)代價。
同一算法，在大規模集合操作中，比如在一個數組中查找某一個數據，可能很快就找到了，可能要耗費很長時間才能找到。因此，在有關算法的研究和分析中，人們主要關注算法的最壞情況代價，有時也關注算法的平均代價。
“大O記法"描述算法性質：
? ? ? ? 時間復雜度：T(n)=O(g(n))
? ? ? ? 空間復雜度：S(n)=O(g(n))
常用的復雜度函數：
????????O(1) ---- 常量復雜度
? ? ? ? O(log n) --- 對數復雜度
? ? ? ? O(n)? ----- 線性復雜度
? ? ? ? O(nlog n)
? ? ? ? O(n^2) --- 平方復雜度
? ? ? ? O(n^3) ---- 立方復雜度
? ? ? ? O(2^n) ---- 指數復雜度
1.3.3、算法分析
0.基本操作，認為其時間復雜度為O(1)。如果是函數調用，應該將其時間復雜度代入，參與整體時間復雜度的計算。
1.加法規則（順序復合)。如果算法（或所考慮算法片段)是兩個部分(或多個部分)的順序復合，其復雜性是這兩部分(或多部分)的復雜性之和。以兩個部分為例:
????????T(n)=Ti(n)＋T(n)=O(T (n))+O(T2 (n))=O(max (T(n), T2 (n)))
其中T;(n)和T(n)分別為順序復合的兩個部分的時間復雜度。由于忽略了常量因子，加法等價于求最大值,取T(n)和 T2(n)中復雜度較高的一個。
2.乘法規則(循環結構)。如果算法（或所考慮的算法片段)是一個循環，循環體將執行T(n)次，每次執行需要T(n)時間，那么:
????????T(n)一T(n)×T2(n)=O(T (n)×O(T(n))=O(T(n)×T2(n))
3.取最大規則(分支結構)。如果算法（或所考慮算法片段)是條件分支，兩個分支的時間復雜性分別為T(n)和 T2(n)，則有:
????????T(n)=O(max(T(n),T2(n)))
1.4、數據結構
數據結構(data structure)研究數據之間的關聯和組合的形式，總結其中的規律性，發掘特別值得注意的有用結構，研究這些結構的性質，進而研究如何在計算機里實現這些有用的數據結構，以支持相應組合數據的高效使用，支持處理它們的高效算法。
典型數據結構：集合結構、序列結構、層次結構、樹形結構、圖形結構
用數據結構存儲信息，不僅要考慮如何把抽象的數據結構映射到計算機或程序可以表達操作的數據存儲形式，還要考慮作用于具體數據結構的各種操作，如結構的建立、其中元素的訪問、插入或刪除元素等一般性操作。
數據結構上的操作需要通過算法實現。
?
1.4.3、python對象和數據結構
Python變量的值都是對象,可以是基本整數、浮點數等類型的對象,也可以是組合類型的對象,如 list等。
Python語言中變量的這種實現方式稱為變量的引用語義，在變量里保存值(對象）的引用。采用這種方式，變量所需的存儲空間大小一致，因為其中只需要保存--個引用。
Python里面的內存管理系統：變量在棧區，值在堆區。
?Python程序內部有一個存儲管理系統，負責管理可用內存，為各種對象安排存儲，支持靈活有效的內存使用。
python標準的數據結構：list(表)、tuple(元組)、dict(字典).
