算法基礎
一：什麼是算法與大O表示法
算法是一組完成任務的指令。任何代碼片段都可視爲算法。
算法是一種通過有限過程解決問題的解決方案。
大O 表示法：
大O表示法是一種特殊的表示法，指出了算法的速度有多快；
大O表示法讓你能夠比較操作數，它指出了算法運行時間的增速；
大O 表示法指出了最糟情況下的運行時間。
舉例，假設列表包含n個元素：
簡單查找需要檢查每個元素，因此需要執行n次操作。使用大O表示法，這個運行時間爲 O(n)。
二分查找需要執行log n次操作。使用大O表示法，這個運行時間爲 O(log n)。
二：算法相關數據結構介紹
1，數組
數組中的元素在內存中都是相連的（緊靠在一起的）。當增加元素時，要請求計算機重新分配一塊可容納所有元素的內存，再將所有元素都移到那裏。
需要隨機地讀取元素時，數組的效率很高，因爲可迅速找到數組的任何元素。數組隨機讀取某個元素的時間複雜度爲O(1)。
在同一個數組中，所有元素的類型都必須相同（都爲int、double等）。
#將python中的list轉換爲數組（list中的所有元素的類型必須相同）
import array
arr = array.array('i',[0,1,1,2,3])
2，鏈表
鏈表中的元素可存儲在內存的任何地方；鏈表的每個元素都存儲了下一個元素的地址，從而使一系列隨機的內存地址串在一起。
鏈表的問題：無法直接讀取鏈表的最後一個元素，因爲你不知道它所處的地址，必須先訪問元素#1，依次下去；跳躍取值時，效率很低。
鏈表的優勢在插入元素和刪除元素方面。
使用鏈表時，插入元素很簡單，只需修改它前面的那個元素指向的地址。
使用數組時，則必須將後面的元素都向後移；如果沒有足夠的空間，可能還得將整個數組複製到其他地方！
因此，當需要在中間插入元素時，鏈表是更好的選擇。
要刪除一個元素，鏈表也是更好的選擇，因爲只需修改前一個元素指向的地址即可。而使用數組時，刪除元素後，必須將後面的元素都向前移。
python實現單鏈表：
class Node:
def __init__(self,data=None):
self.data = data
self.next = None
def __repr__(self):
return str(self.data)
class LinkedList:
def __init__(self):
self.head = None
self.length = 0
def is_empty(self):
return self.length == 0
def append(self,item):
if isinstance(item,Node):
this_node = item
else:
this_node = Node(data=item)
if self.head == None:
self.head = this_node
else:
node = self.head
while node.next:
node = node.next
node.next = this_node
self.length += 1
def insert(self,index,item):
if type(index) is int:
if index < 0 or index >= self.length:
print("Index value is out of range.")
return
this_node = Node(data=item)
current_node = self.head
if index == 0:
self.head = this_node
this_node.next = current_node
return
while index - 1:
current_node = current_node.next
index -= 1
this_node.next = current_node.next
current_node.next = this_node
self.length += 1
return
else:
print("Index value is not int.")
return
def delete(self,index):
if type(index) is int:
if index < 0 or index >= self.length:
print("Index value is out of range.")
return
if index == 0:
self.head = self.head.next
else:
current_node = self.head
while index - 1:
current_node = current_node.next
index -= 1
this_node = current_node.next
current_node.next = this_node.next
self.length -= 1
return
else:
print("Index value is not int.")
return
def __repr__(self):
if self.is_empty():
print("Linked list is empty")
else:
nlist = ""
node = self.head
nlist += "Head-->" + node.data + " "
while node.next:
node = node.next
nlist += "-->" + node.data + " "
return nlist
3，棧，隊列，雙端隊列
棧 stack ：一個有序的項的集合。添加項和移除項發生在同一端，即後進先出，形式如「彈夾」「疊盤子」。
隊列 queue：一系列有序的元素的集合。先進先出，形式如「排隊」。
雙端隊列 deque：一系列有序的元素的集合。允許從兩端插入和從兩端刪除。
python實現棧：
class Stack: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def peek(self): return self.items[-1] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def size(self): return len(self.items)
三：查找算法之二分法
二分查找只能查找有序的元素列表！這個前提條件得記住。
二分法思路：先取列表中間值與查找元素比較，若查找元素小於中間值，則在小於中間值的那一半列表中再取中間值與查找元素比較，以此類推，直到找到該元素。
一般而言，對於包含n個元素的列表，用二分查找最多需要log n步，所以二分法的時間複雜度爲O(log n)。
def binary_search(list,item):
low = 0
high = len(list)-1
while low <= high:
mid = (low + high)//2
guess = list[mid]
if guess == item:
return mid
elif guess < item:
low = mid + 1
else:
high = mid -1
return None
四：查找算法之散列表
散列表（Hash table），也叫哈希表，是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
散列表(hash table)是實現字典操作的一種有效的數據結構。
儘管最壞的情況下，散列表中查找一個元素的時間與鏈表中查找的時間相同，達到了O(n)。
然而實際應用中，散列的查找的性能是極好的。在一些合理的假設下，在散列表中查找一個元素的平均時間是O(1)。
散列函數是這樣的函數，即無論你給它什麼數據，它都還你一個數字（即將輸入映射到數字）：
1，它必須是一致的，相同的輸入始終映射到同一個數字；
2，它應將不同的輸入映射到不同的數字
建立散列表操作步驟：
1) step1 取數據元素的關鍵字key，計算其哈希函數值（地址）。若該地址對應的存儲空間還沒有被佔用，則將該元素存入；否則執行step2解決衝突。
2) step2 根據選擇的衝突處理方法，計算關鍵字key的下一個存儲地址。若下一個存儲地址仍被佔用，則繼續執行step2，直到找到能用的存儲地址爲止。
衝突處理方法：
影響哈希查找效率的一個重要因素是哈希函數本身。當兩個不同的數據元素的哈希值相同時，就會發生衝突。爲減少發生衝突的可能性，哈希函數應該將數據儘可能分散地映射到哈希表的每一個表項中。
解決衝突的方法有以下兩種：
(1) 開放地址法
(2) 鏈地址法
注：Python字典dict的實現是使用開放地址法中的二次探查來解決衝突的。
五：排序算法之冒泡排序、選擇排序、插入排序
1，冒泡排序--時間複雜度：O(n²)
冒泡排序：對一個列表多次重複遍歷，比較相鄰的兩項，對排錯的項進行交換順序。每遍歷一次，就有一個最大項排在了正確的位置。
def bubble_sort(alist): for passnum in range(len(alist)-1,0,-1): for i in range(passnum): if alist[i] > alist[i+1]: alist[i],alist[i+1] = alist[i+1],alist[i]
短路冒泡排序：冒泡排序改良版；如果在某次遍歷過程中沒有交換，我們就可斷定列表已經排好。這樣就可以使冒泡排序在已知列表排好的情況下提前結束。
def short_bubble_sort(alist): exchanges = True passnum = len(alist)-1 while passnum > 0 and exchanges: exchanges = False for i in range(passnum): if alist[i] > alist[i+1]: exchanges = True alist[i],alist[i+1] = alist[i+1],alist[i] passnum -= 1
2，選擇排序--時間複雜度：O(n²)
選擇排序提高了冒泡排序的性能，它每遍歷一次列表只交換一次數據，即進行一次遍歷時找到最大的項，完成遍歷後，再把它換到正確的位置。
#選擇排序代碼一
def find_smallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1,len(arr)):
if arr[i]<smallest:
smallest=arr[i]
smallest_index=i
return smallest_index
def selection_sort(arr):
new_arr = []
for i in range(len(arr)):
smallest_index = find_smallest(arr)
new_arr.append(arr.pop(smallest_index))
return new_arr
#選擇排序代碼二 def selection_sort(alist): for passnum in range(len(alist)-1,0,-1): maxnum = 0 for i in range(1,passnum+1): if alist[i] > alist[maxnum]: maxnum = i alist[i],alist[maxnum] = alist[maxnum],alist[i]
3，插入排序--時間複雜度：O(n²)
插入排序：從第二個元素開始，每個元素依次與前面的有序子列表比較，直到找到自己的位置，插入，跳出本次遍歷。
def insertion_sort(alist): for i in range(1,len(alist)): for j in range(i): if alist[i] < alist[j]: alist.insert(j,alist.pop(i)) break
六：什麼是遞歸，什麼是分而治之
1，遞歸
遞歸指的是調用自己的函數。
Leigh Caldwell在Stack Overflow上說：「如果使用循環，程序的性能可能更高；如果使用遞歸，程序可能更容易理解。如何選擇要看什麼對你來說更重要」。
編寫遞歸函數時，必須告訴它何時停止遞歸。正因爲如此，每個遞歸函數都有兩部分：基線條件（base case）和遞歸條件（recursive case）。遞歸條件指的是函數調用自己，而基線條件則指的是函數不再調用自己，從而避免形成無限循環。
計算機在內部使用被稱爲調用棧的棧。通過調用棧來理解遞歸是一種好方法。
def greet(name):
print "hello, " + name + "!"
greet2(name)
print "getting ready to say bye..."
bye()
def greet2(name):
print "how are you, " + name + "?"
def bye():
print "ok bye!"
#遞歸函數
def fact(x):
if x == 1:
return 1
else:
return x * fact(x-1)
2，分而治之
分而治之（divide and conquer，D&C）—— 一種著名的遞歸式問題解決方法。
D&C算法是遞歸的。使用D&C解決問題的過程包括兩個步驟。
(1) 找出基線條件，這種條件必須儘可能簡單。
(2) 不斷將問題分解（或者說縮小規模），直到符合基線條件。
舉例：要將下面這塊地均勻地分成方塊，且分出的方塊要儘可能大，試試用分而治之解決。
歐幾里得算法：適用於這小塊地的最大方塊，也是適用於整塊地的最大方塊。
注：均勻分上面這塊地的適用的最大方塊爲80 m× 80 m。
七：排序算法之快速排序、歸併排序
1，快速排序
快速排序是一種常用的排序算法，比選擇排序快得多。快速排序使用了D&C(分而治之)。
快速排序最佳情況也是平均情況的時間複雜度：O(nlogn)；最糟情況下爲 O(n²)。
快速排序思路：
(1) 選擇基準值。
(2) 將數組分成兩個子數組：小於基準值的元素和大於基準值的元素。
(3) 對這兩個子數組進行快速排序。（遞歸）
def quicksort(arr): if len(arr)<2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quicksort(less) + [pivot] + quicksort(greater)
2，歸併排序
歸併排序（MERGE-SORT）是建立在歸併操作上的一種有效的排序算法,該算法是採用分治法（D&C）的一個非常典型的應用。
歸併排序的時間複雜度始終爲O(nlogn)！
歸併排序原理：
一、將一個序列從中間位置分成兩個子序列；
二、再將這兩個子序列按照第一步繼續二分下去；
三、直到所有子序列的長度都爲1，此時可以認爲這些子序列是有序序列；
四、依次兩兩合併有序序列，最終得到一個完整的有序序列。
def merge_list(alist,blist): clist = [] i = j = 0 while i < len(alist) and j < len(blist): if alist[i] < blist[j]: clist.append(alist[i]) i += 1 else: clist.append(blist[j]) j += 1 while i < len(alist): clist.append(alist[i]) i += 1 while j < len(blist): clist.append(blist[j]) j += 1 return clist def merge_sort(tlist): if len(tlist) <= 1: return tlist middle = len(tlist)//2 left = merge_sort(tlist[:middle]) right = merge_sort(tlist[middle:]) return merge_list(left,right)
八：數據結構之樹、圖簡介
1，樹
節點（Node）是樹的基本構成部分。它可以有其他專屬的名稱，我們稱之爲「鍵（key）」。 一個節點可能有更多的信息，我們稱之爲「負載（payload）」。
邊（Edge）也是另一個樹的基本構成部分。邊連接兩個節點，並表示它們之間存在聯繫。每個節點（除了根節點）都有且只有一條與其他節點相連的入邊（指向該節點的邊），每個節點可能有許多條出邊（從該節點指向其他節點的邊）。
根節點是樹中唯一一個沒有入邊的節點。
路徑是由邊連接起來的節點的有序排列。例如：動物界 → 脊索動物門 → 哺乳動物綱 → 食肉動物目 → 貓科 → 貓屬 → 家貓 就是一條路徑。
同一個節點的所有子節點互爲兄弟節點。
沒有子節點的節點成爲稱爲葉節點。
一個節點的層數是指從根節點到該節點的路徑中的邊的數目。定義根節點的層數爲0。
樹的高度等於所有節點的層數的最大值。
樹的定義一：樹是節點和連接節點的邊的集合。
樹的定義二：一棵樹有根和其他子樹組成，這些子樹也是樹。
二叉樹：每個節點最多含有兩個子樹的樹稱爲二叉樹
堆（heap)是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。堆總是一棵完全二叉樹。
2，圖
圖模擬一組連接；圖由節點（node）和邊（edge）組成。一個節點可能與衆多節點直接相連，這些節點被稱爲鄰居。
圖用於模擬不同的東西是如何相連的。
有向圖：其中的關係是單向的
無向圖：沒有箭頭，直接相連的節點互爲鄰居
最短路徑問題（shorterst-path problem）
(1) 使用圖來建立問題模型。
(2) 使用廣度優先搜索解決問題。
廣度優先搜索是一種用於圖的查找算法，可幫助回答兩類問題：
第一類問題：從節點A出發，有前往節點B的路徑嗎？
第二類問題：從節點A出發，前往節點B的哪條路徑最短？
廣度優先搜索實現算法：
graph = {"rock":["mike1","mike2","mike3"],"mike1":["jack1","jack2"],"jack1":[],"jack2":[],
"mike2":["rock","mike1","mike3"],"mike3":["mike2","rock","manmm"],"manmm":[]}
def person_is_seller(name):
return name[-1] == "m"
from collections import deque
def search(name):
search_queue = deque()
search_queue += graph[name]
searched = []
while search_queue:
person = search_queue.popleft()
if not person in searched:
if person_is_seller(person):
print(person + " is a mango seller.")
return True
else:
search_queue += graph[person]
searched.append(person)
return False
廣度優先搜索的運行時間爲O(人數 + 邊數)，這通常寫作O(V + E)，其中V爲頂點（vertice）數，E爲邊數。