1.大O表示法是一種特殊的表示法，指出了算法的速度有多快。O（n）

小結(jié)：

二分查找的速度比簡單查找快得多。

O (log n )比O (n )快。需要搜索的元素越多，前者比后者就快得越多。

算法運行時間并不以秒為單位。

算法運行時間是從其增速的角度度量的。

算法運行時間用大O表示法表示。

2.鏈表和數(shù)組

鏈表中的元素可存儲在內(nèi)存的任何地方。

數(shù)組和鏈表哪個用得更多呢？顯然要看情況。但數(shù)組用得很多，因為它

支持隨機訪問。有兩種訪問方式：隨機訪問 和順序訪問 。順序訪問意

味著從第一個元素開始逐個地讀取元素。鏈表只能順序訪問：要讀取鏈

表的第十個元素，得先讀取前九個元素，并沿鏈接找到第十個元素。隨

機訪問意味著可直接跳到第十個元素。本書經(jīng)常說數(shù)組的讀取速度更

快，這是因為它們支持隨機訪問。很多情況都要求能夠隨機訪問，因此

數(shù)組用得很多。

小結(jié)：

計算機內(nèi)存猶如一大堆抽屜。

需要存儲多個元素時，可使用數(shù)組或鏈表。

數(shù)組的元素都在一起。

鏈表的元素是分開的，其中每個元素都存儲了下一個元素的地址。

數(shù)組的讀取速度很快。

鏈表的插入和刪除速度很快。

在同一個數(shù)組中，所有元素的類型都必須相同（都為int、double等）。

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
        if guess >item:
            high=mid-1
        else:
            low=mid+1
    return None
my_list=[1,3,5,7,9]
print(binary_search(my_list,3))
    
def findsmallest(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 selectionsort(arr):
    newarr=[]
    for i in range(len(arr)):
        smallest=findsmallest(arr)
        newarr.append(arr.pop(smallest))
    return newarr

print(selectionsort([5,3,6,2,10]))

def countdown(i):
    '''遞歸'''
    print(i)
    if i <=0:  #基線條件
        return
    else:      #遞歸條件
        countdown(i-1)

print(countdown(5))

3.遞歸指的是調(diào)用自己的函數(shù)。
每個遞歸函數(shù)都有兩個條件：基線條件和遞歸條件。
棧有兩種操作：壓入和彈出。
所有函數(shù)調(diào)用都進入調(diào)用棧。
調(diào)用棧可能很長，這將占用大量的內(nèi)存。
4.排序
D&C將問題逐步分解。使用D&C處理列表時，基線條件很可能是空數(shù)組或只包含一個元素的數(shù)組。
實現(xiàn)快速排序時，請隨機地選擇用作基準值的元素?？焖倥判虻钠骄\行時間為O (n log n )。
大O表示法中的常量有時候事關(guān)重大，這就是快速排序比合并排序快的原因所在。
比較簡單查找和二分查找時，常量幾乎無關(guān)緊要，因為列表很長
時，O (log n )的速度比O (n )快得多。

def quicksort(array):
    '''快速排序'''
    if len(array)<2: #基線條件
        return array
    else:#遞歸條件
        pivot=array[0]
        less=[i for i in array[1:] if i<=pivot]
        greater=[i for i in array[1:] if i>pivot]
        return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([10,5,2,3]))

5.散列表在python中就是字典
無論你訪問哪個網(wǎng)站，其網(wǎng)址都必須轉(zhuǎn)換為IP地址。這不是將網(wǎng)址映射到IP地址嗎？好像非常適合使用散列表啰！這個過程被稱為DNS解析 （DNS resolution），散列表是提供這種功能的方式之一。（google.com-74.123.139.3）
散列表適合用于：
仿真映射關(guān)系；
防止重復(fù)；
緩存/記住數(shù)據(jù)，以免服務(wù)器再通過處理來生成它們。
如果兩個鍵映射到了同一個位置，就在這個位置存儲一個鏈表。
散列函數(shù)很重要 。前面的散列函數(shù)將所有的鍵都映射到一個位置，而最理想的情況是，散列函數(shù)將鍵均勻地映射到散列表的不同位置。
如果散列表存儲的鏈表很長，散列表的速度將急劇下降。然而，如果使用的散列函數(shù)很好 ，這些鏈表就不會很長！
你可以結(jié)合散列函數(shù)和數(shù)組來創(chuàng)建散列表。
沖突很糟糕，你應(yīng)使用可以最大限度減少沖突的散列函數(shù)。
散列表的查找、插入和刪除速度都非?？?。
散列表適合用于仿真映射關(guān)系。
一旦填裝因子超過0.7，就該調(diào)整散列表的長度。
散列表可用于緩存數(shù)據(jù)（例如，在Web服務(wù)器上）。
散列表非常適合用于防止重復(fù)。
6.廣度優(yōu)先搜索指出是否有從A到B的路徑。
如果有，廣度優(yōu)先搜索將找出最短路徑。
面臨類似于尋找最短路徑的問題時，可嘗試使用圖來創(chuàng)建模型，再使用廣度優(yōu)先搜索來解決問題。
有向圖中的邊為箭頭，箭頭的方向指定了關(guān)系的方向，例如，rama→adit表示rama欠adit錢。
無向圖中的邊不帶箭頭，其中的關(guān)系是雙向的，例如，ross - rachel表示“ross與rachel約會，而rachel也與ross約會”。
隊列是先進先出（FIFO）的。
棧是后進先出（LIFO）的。
你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必須是隊列。
對于檢查過的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無限循環(huán)。

from collections import deque 
graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["bob"] = ["anuj", "peggy"]
graph["alice"] = ["peggy"]
graph["claire"] = ["thom", "jonny"]
graph["anuj"] = []
graph["peggy"] = []
graph["thom"] = []
graph["jonny"] = []
def search(name):
    '''廣度優(yōu)先搜索算法'''
    search_queue=deque()
    search_queue += graph[name]
    searched=[]
    while search_queue:
        person=search_queue.popleft()
        if person not in searched:
            if person_is_seller(person):
                print(person+"id a mango seller!")
                return True
            else:
                search_queue += graph[person]
                searched.append(person)
    return False
def person_is_seller(name):
    return name[-1] == 'm'

print(search("bob"))

graph = {}
graph["you"] = ["alice", "bob", "claire"]
graph["start"] = {}#權(quán)重
graph["start"]["a"] = 6
graph["start"]["b"] = 2
graph["a"] = {}
graph["a"]["fin"] = 1
graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5
graph["fin"] = {} #終點沒有任何鄰居
infinity = float("inf")#無窮大
costs = {}#創(chuàng)建開銷列表
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity
parents = {}#父點散列表
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None
processed = []#記錄處理過的節(jié)點

def find_lowest_cost_node(costs):
    '''迪杰斯特拉算法'''
    lowest_cost = float("inf")
    lowest_cost_node = None
    for node in costs:#遍歷所有的節(jié)點
        cost = costs[node]
        if cost < lowest_cost and node not in processed: #如果當前節(jié)點的開銷更低且未處理過，
            lowest_cost = cost#就將其視為開銷最低的節(jié)點
            lowest_cost_node = node
    return lowest_cost_node
node = find_lowest_cost_node(costs) #在未處理的節(jié)點中找出開銷最小的節(jié)點
while node is not None:#這個while循環(huán)在所有節(jié)點都被處理過后結(jié)束
    cost = costs[node]
    neighbors = graph[node]
    for n in neighbors.keys():#遍歷當前節(jié)點的所有鄰居
        new_cost = cost + neighbors[n]
        if costs[n] > new_cost: #如果經(jīng)當前節(jié)點前往該鄰居更近，
            costs[n] = new_cost #就更新該鄰居的開銷
            parents[n] = node #同時將該鄰居的父節(jié)點設(shè)置為當前節(jié)點
    processed.append(node) #將當前節(jié)點標記為處理過
    node = find_lowest_cost_node(costs)#找出接下來要處理的節(jié)點，并循環(huán)

print(find_lowest_cost_node[6])

廣度優(yōu)先搜索用于在非加權(quán)圖中查找最短路徑。
狄克斯特拉算法用于在加權(quán)圖中查找最短路徑。
僅當權(quán)重為正時狄克斯特拉算法才管用。
如果圖中包含負權(quán)邊，請使用貝爾曼-福德算法。

states_needed = set(["mt", "wa", "or", "id", "nv", "ut","ca", "az"]) #你傳入一個數(shù)組，它被轉(zhuǎn)換為集合
stations = {}
stations["kone"] = set(["id", "nv", "ut"])
stations["ktwo"] = set(["wa", "id", "mt"])
stations["kthree"] = set(["or", "nv", "ca"])
stations["kfour"] = set(["nv", "ut"])
stations["kfive"] = set(["ca", "az"])
final_stations = set()
best_station = None
states_covered = set()
for station, states_for_station in stations.items():
    covered = states_needed & states_for_station #它計算交集
    if len(covered) > len(states_covered):
        best_station = station
        states_covered = covered
        
    states_needed -= states_covered
    final_stations.add(best_station)
    print(final_stations)

貪婪算法尋找局部最優(yōu)解，企圖以這種方式獲得全局最優(yōu)解。
對于NP完全問題，還沒有找到快速解決方案。
面臨NP完全問題時，最佳的做法是使用近似算法。
貪婪算法易于實現(xiàn)、運行速度快，是不錯的近似算法。