• 二分查找

  • 輸入：有序列表個元素，最多步找到计呈，與簡單查找相比最多需要n步

  • 輸出：找到的位置/

  • 數(shù)據(jù)結構：使用數(shù)組周霉，不斷更新首尾index（low,high）

  • def binary_search(list, item):
        low = 0
        high = len(list)-1
        while low <= high:  #只要范圍沒有縮小到只含1個元素
            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))    #1
    print(binary_search(my_list, -1))   #None
    

• 算法運行時間用表示,由快到慢的5中：

  • :對數(shù)時間姚炕，e.g.二分法
  • :線性時間摊欠，e.g.簡單查找
  • : 快速排序，合并排序
  • ：選擇排序
  • : e.g. 旅行商問題柱宦，一種非常慢的算法
  • 算法的速度指的并非時間些椒，而是操作數(shù)的增速
  • 談了算法速度，隨著輸入的增加掸刊，運行時間將以什么樣的速度增加

• 旅行商問題：

  • 問題描述：前往n個城市免糕，同時確保旅程最短，對每種順序都需要計算總旅程忧侧，再挑選旅程最短的路線
  • 近似答案石窑，見K近鄰

• 數(shù)組和鏈表：

  • 數(shù)組：元素內存中相連，同一數(shù)組中蚓炬，所有元素類型必須相同松逊，支持順序訪問+隨機訪問（被應用的更多）

  • 鏈表：元素可存儲在內存的任何地方，只支持順序訪問

    	數(shù)組	鏈表
    讀取
    插入
    刪除		[如何能夠立即訪問要刪除的元素時]

• 選擇排序：

  • 雙層循環(huán)肯夏，時間復雜度

  • 解釋1：遍歷待排序列表经宏，找出列表中最小/最大的元素，將該元素添加到一個新的列表中驯击，將該元素從原列表中刪除烁兰。

  • 解釋2：首先，找到數(shù)組中最小的元素徊都，拎出來沪斟，將它和數(shù)組的第一個元素交換位置，第二步暇矫，在剩下的元素中繼續(xù)尋找最小的元素币喧，拎出來轨域，和數(shù)組的第二個元素交換位置，如此循環(huán)杀餐，直到整個數(shù)組排序完成。至于選大還是選小朱巨，這個都無所謂史翘，你也可以每次選擇最大的拎出來排，也可以每次選擇最小的拎出來的排冀续，只要你的排序的手段是這種方式琼讽，都叫選擇排序

  • 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))#.pop返回移除的元素值
        return newArr
    print(selectionSort([5,3,6,2,10]))
    

• 隊列：先進先出（First In First Out, FIFO）

  • 類似于棧，不能隨機地訪問隊列中的元素洪唐，只支持兩種操作：入隊和出隊

• 調用棧（call stack）：后進先出(Last In First Out, LIFO)

  • 用于存儲多個函數(shù)的變量即調用棧钻蹬。所有函數(shù)調用都進入調用棧
  • 每當調用函數(shù)時，計算機都會將函數(shù)調用涉及的所有變量的值存儲到內存中凭需，當函數(shù)調用返回后问欠，棧頂?shù)膬却鎵K被彈出
  • 棧包含兩種操作：壓入（插入）和彈出（刪除并讀取）粒蜈，棧作為一種數(shù)據(jù)結構顺献，但不能用于查找

• 遞歸

  • 調用自己的函數(shù)即遞歸。原理上枯怖，遞歸與循環(huán)作用相同注整，而遞歸只是讓解決方案更清晰，并沒有性能上的優(yōu)勢度硝。如果使用循環(huán)肿轨，程序性能可能更高，使用遞歸蕊程，程序可能更容易理解椒袍，如果選擇要看什么對你更重要
  • 遞歸函數(shù)包含兩個條件：邊界條件（函數(shù)不再調用自身）和遞歸條件（函數(shù)調用自身）
  • 遞歸函數(shù)也使用調用棧，使用上很方便存捺，幫助跟蹤當前程序執(zhí)行情況槐沼，但會占用較多內存（每個函數(shù)調用都要占用一定內存），如果棧很高捌治，將占用大量內存岗钩，替代方法：
    • 重新編寫代碼，使用循環(huán)
    • 使用尾遞歸肖油，但并非所有語言都支持尾遞歸

• 函數(shù)式編程：

  • 諸如Haskell等函數(shù)式編程語言沒有循環(huán)兼吓，因此只能使用遞歸來編寫即使可以使用循環(huán)就可以輕松實現(xiàn)的函數(shù)

• 分治法（divide and conquer, D&C）：

  • D&C并非可用于解決問題的算法，而是一種解決問題的思路

  • D&C算法是遞歸的森枪，解決該問題的過程包含兩個步驟

  • 步驟1： 找出邊界條件视搏，必須盡可能簡單审孽，在使用D&C處理列表時，邊界條件很可能是空數(shù)組或者只包含一個元素的數(shù)組

  • 步驟2：不斷將問題分解/縮小規(guī)模浑娜，直到符合邊界條件

  • 歐幾里得算法（用來求兩個正整數(shù)最大公約數(shù)的算法）佑力，又稱輾轉相除法，例如求1997與615之間的最大公約數(shù)

    1997=615*3+152
    615=152*4+7
    152=7*21+5
    7=5*1+2
    5=2*2+1
    2=2*1+0（當被加數(shù)為0時筋遭，得出1997與615之間最大公約數(shù)為1）

  • 問題變形：將一塊矩形的土地（1680*640）均勻分成方塊打颤，且分出的方塊要盡可能大

    • 邊界條件：一條邊的長度是另一條邊的整數(shù)倍
    • 遞歸找出剩余面積可容納的最大方塊，1680*640 -> (640*2+400)*640 -> 400*640 -> (400+240)*400 -> 240*400 -> (240+160)*240 -> 160*240 -> (160+80)*160 -> 80*60(邊界條件)

    1680*640 -> (640*2+400)*640
    400*640 -> (400+240)*400
    240*400 -> (240+160)*240
    160*240 -> (160+80)*160
    80*60(邊界條件)漓滔，因此對于（1680*640）的土地编饺，適用的最大方塊為80*80

• 快速排序（最快的排序算法之一）：

  • 核心思想：分治法。它的實現(xiàn)方式是每次從序列中選出一個基準值(pivot)响驴，其他數(shù)依次和基準值做比較透且，比基準值大的放右邊，比基準值小的放左邊（數(shù)組分成兩個子數(shù)組）豁鲤，然后再對左邊和右邊的兩組數(shù)分別選出一個基準值秽誊，進行同樣的比較移動（對這兩個子數(shù)組遞歸進行快速排序），重復步驟畅形，直到最后都變成單個元素养距，整個數(shù)組就成了有序的序列

  • 邊界條件：空數(shù)組/只含一個元素的數(shù)組不用排序

  • 速度取決于pivot的選擇，平均時間復雜度日熬，最壞情況棍厌，實現(xiàn)時應隨機選擇用作pivot的元素

  • 最壞情況：假設總是將第一個元素作為pivot，且要處理的數(shù)組是有序的竖席，數(shù)組并沒有分成兩半耘纱，其中一個子數(shù)組始終為空，使得調用棧很長毕荐，而最佳情況棧長為(最佳情況也是平均情況)束析，每層需要時間均為。因為快速排序不檢查輸入數(shù)組是否有序憎亚，因此它依然嘗試對其進行排序

  • 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]))
    

• 快速排序與合并排序

  • 在大O表示法中员寇，實際上是指，其中指算法所需的固定時間量第美，被稱為常量蝶锋。
  • 常量的影響一般很小，例如對于二分查找（）和簡單查找（）來說什往，在40億個元素列表中查找所需時間扳缕，前者（）后者（），二分查找還是快的多，常量沒什么影響
  • 常量的影響可能很大躯舔，例如對于快速查找和合并查找驴剔，快速查找的常量比合并查找小，如果二者運行時間都是粥庄，快速查找的速度將更快丧失，實際上，快速查找的速度確實更快飒赃，對于最壞情況利花，遇上平均情況的可能性要大得多

• 散列函數(shù)

  • 將輸入映射到數(shù)字
  • 函數(shù)滿足的要求：必須是一致的，即每次輸入相同時载佳，輸出也要相同|||將不同的輸入映射到不同的數(shù)字（在最理想情況，散列函數(shù)將鍵均勻地映射到散列表的不同位置）
  • 良好的散列函數(shù)：讓數(shù)組中的值呈均勻分布臀栈，可以使用SHA函數(shù)

• 填裝因子

  • 
  • 度量散列表中有多少位置是空的蔫慧，一旦填裝因子開始增大，需要調整長度（resizing）,通常將數(shù)組增長一倍权薯，然后使用函數(shù)hash將所有元素插入到新的散列表中
  • 一個不錯的經驗：一旦,就調整散列表的長度

• 沖突(collision)

  • 給兩個鍵分配的位置相同姑躲。處理方法：若兩個鍵映射到同一位置，就在該位置存儲一個鏈表盟蚣，單鏈表長度過長時黍析，散列表的速度就會很慢（散列函數(shù)設計不好時，如果使用的散列函數(shù)很好屎开，鏈表就不會很長）
  • 避免沖突需要有：較低的填裝因子|||良好的散列函數(shù)

• 散列表(hash table)

  • 也被成為散列映射阐枣、映射、字典奄抽、關聯(lián)數(shù)組蔼两，適合用于模擬映射關系，用于防止重復等場景

  • 使用散列函數(shù)和數(shù)組創(chuàng)建的數(shù)據(jù)結構：散列表（一種包含額外邏輯的數(shù)據(jù)結構）逞度，因為使用數(shù)組來存儲數(shù)據(jù)额划，因此其獲取元素的速度與數(shù)組一樣快

  • 與數(shù)組和鏈表直接映射到內存不同，散列表使用散列函數(shù)來確定元素的存儲位置

  • 散列表由鍵和值組成档泽。無需自己實現(xiàn)散列表俊戳，任一優(yōu)秀的語言都提供了散列表實現(xiàn)，e.g. python提供的散列表實現(xiàn)為字典馆匿，可使用dict()來創(chuàng)建散列表抑胎，如果使用list()進行查找，只能使用簡單查找甜熔，速度會很慢

  • 散列表性能：平均情況圆恤，被稱為常量時間，表示不管散列表多大，所需時間都相同盆昙，兼具數(shù)組和鏈表的優(yōu)點

    	散列表（平均情況）	散列表（最壞情況）	數(shù)組	鏈表
    查找
    插入
    刪除

  • 應用1：用于查找：基于姓名查找號碼的電話簿羽历、DNS解析

  • 應用2：用于緩存：一種常用的加速方式，提高網站的訪問速度淡喜，用戶能夠更快看到網頁秕磷，且服務器需要做的工作更少，緩存的數(shù)據(jù)存儲在散列表中炼团，鍵和值分別為url和頁面數(shù)據(jù)

• 圖：

  • 由節(jié)點和邊組成澎嚣，直接相連的節(jié)點成為鄰居，分為有向圖瘟芝、無向圖
  • 實現(xiàn)：散列表易桃，鍵：節(jié)點，值：節(jié)點的鄰居構成的列表

• 廣度優(yōu)先搜索（breadth-first search, BFS）

  • BFS是一種用于圖的查找算法

  • 解決A,B兩點之間是否有路/A,B兩點之間最短路徑問題的算法：首先使用圖建立問題模型锌俱，其次使用BFS解決問題

  • 應用：編寫國際跳棋AI晤郑，計算最少走多少步就可以獲勝|||編寫拼寫檢查器，計算最少編輯多少個地方就可將錯拼的單詞改為正確的單詞|||根據(jù)人際關系網絡找到關系最近的醫(yī)生

  • 實現(xiàn)：隊列贸宏，在python中可使用函數(shù)deque創(chuàng)建一個雙端隊列造寝，需要維護數(shù)組保存已檢查過的人（searched），防止程序形成無限循環(huán)（e.g. 圖中只包含兩個節(jié)點吭练，雙向邊）诫龙。算法將不斷執(zhí)行直到滿足以下條件之一：

    • 找到一位芒果經銷商
    • 隊列變空，即你的人際關系網中沒有芒果經銷商

  • 運行時間：,其中為頂點（使用隊列）鲫咽，為邊數(shù)（在整個關系網中搜索）签赃。

  • from collection import deque
    def search(name):
        search_queue = deque()#創(chuàng)建一個隊列
        search_queue += graph[name]#將鄰居（數(shù)組）都加入到這個搜索隊列中
        searched = []#這個數(shù)組用于記錄檢查過的人
        while sear_queue:#只要隊列不為空
            person = search_queue.popleft()#就取出其中的第一個人
            if person_is_seller(person):#檢查這個人是否為芒果經銷商
                print(person+' is a mango seller!')
                return True
            else:
                search_queue += graph[person]#不是，將這個人的朋友都加入到隊列中
                searched.append(person)#將這個人標記為檢查過
        return False
    
    def person_is_seller(name):
        return name[-1] == 'm'
    

• Dijkstra算法

  • 廣度優(yōu)先搜索的應用場景針對圖中邊權重相同的情況【非加權圖】浑侥，找到的“最短路徑”是指段數(shù)最少姊舵。當圖中邊的權重不同時【加權圖】，需要使用Dijkstra算法寓落，只適用于權重為正的有向無環(huán)圖（DAG）【使用散列表graph維護節(jié)點和有向邊的權重】,即應用在有向圖的場景下【無向圖中每條邊都是一個環(huán)括丁，繞環(huán)的路徑不可能是最短路徑】，找出的是總權重最小的路徑伶选。
  • 算法步驟：
    • 找出可在最短時間內到達的節(jié)點
    • 如果找到前往該節(jié)點的鄰居的更短路徑史飞，更新該節(jié)點的鄰居開銷【維護costs散列表，維護節(jié)點和其開銷】
    • 重復這個過程仰税，直到對圖中的每個節(jié)點都這樣做了
    • 計算最終路徑【維護parent散列表存儲節(jié)點和其父節(jié)點构资，用于最終回溯】
  • 算法假設：對處理過的節(jié)點，沒有前往該節(jié)點的更短路徑
  • 負權邊
    • 負權邊無法使用該算法
    • 不滿足算法假設（可能先增后減能夠獲取更短路徑）
    • 使用Bellman-Ford算法

  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é)點都被處理過后結束
      cost = costs[node]
      neighbors = graph[node]
      for n in neighbors.keys():#遍歷當前節(jié)點的所有鄰居
          new_cost = cost + neighbors[n]#開銷指從起點前往該節(jié)點需要多長時間
          if costs[n] > new_cost:#如果經當前節(jié)點前往該鄰居更近
              costs[n] = new_cost#就更新該鄰居的開銷
              parents[n] = node#同時將該鄰居的父節(jié)點設置為當前節(jié)點
      processed.append(node)#將當前節(jié)點標記為處理過
      node = find_lowest_cost_node(costs)#找出接下來要處理的界定啊陨簇，并循環(huán)
  

• 貪婪算法

  • 尋找局部最優(yōu)解吐绵，企圖以這種方式獲得全局最優(yōu)解，易于實現(xiàn)，運行速度快己单，是不錯的近似算法
  • 調度問題：根據(jù)課表唉窃，將盡可能多的課安排在某間教室上
    • 每次都選擇結束最早的課，后選的開始時間要晚于之前的結束時間（貪婪思想）
  • 集合覆蓋問題：你辦了個廣播節(jié)目纹笼，要讓全美50個州的聽眾都聽到纹份，需要決定節(jié)目在哪些廣播臺播出，每個廣播臺播出需要支付費用廷痘，力圖在盡可能少的廣播臺播出蔓涧，每個廣播臺都覆蓋特定的區(qū)域，不同廣播臺覆蓋區(qū)域可能重疊
    • 列出每種可能廣播臺集合（精確解）笋额，可能子集有,因此運行時間
    • 貪婪算法（近似解）：選出這樣一個廣播臺元暴，即它覆蓋了最多的未覆蓋州，即便這個廣播臺覆蓋了一些已覆蓋的州也沒關系兄猩。重復第一步昨寞，直到覆蓋了所有的州。運行時間

while states_needed:
    best_station = None#覆蓋了最多的未覆蓋州的廣播臺
    states_covered = set()#包含該廣播臺覆蓋的所有未覆蓋的州
    for station, states in stations.items():
        covered = states_needed & states#集合交集
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered 
  states_needed -= states_covered
    final_stations.add(best_station)#存儲最終選擇的廣播臺

• 近似算法優(yōu)劣標準：

  • 速度有多快
  • 近似解與最優(yōu)解的接近程度

• NP完全問題

  • 集合覆蓋問題：為橄欖球隊挑選隊員厦滤，清單上列出對球隊的所有要求，球隊名額有限歼狼，每個候選球員都滿足某些需求掏导。
    • 近似求解：找出符合最多要求的球員，不斷重復這個過程直到球隊滿足要求（或名額已滿）
  • 旅行商問題：近似算法（找到較短路徑即可）羽峰，具體的趟咆，隨便選擇出發(fā)城市，每次選擇要去的下一個城市時梅屉，都選擇還沒去的最近的城市
    • 找出經由指定幾個點的最短路徑即旅行商問題——NP完全問題
    • 不指定途徑點值纱，單純求解兩點之間的最短路徑即Dijkstra算法
  • 兩問題共同點：需計算所有解，并從中選出最小/最短的那個
  • NP完全問題：沒有找到快速求解精確解的方法坯汤，最佳的做法即使用近似算法虐唠。但判斷問題是否為NP完全問題很難， 易于解決的問題和NP完全問題的差別通常很小惰聂。以下是一些tips：
    • 元素較少時算法運行速度非辰ィ快，隨著元素數(shù)量增加搓幌，速度會變得非常慢
    • 涉及“所有組合”的問題通常是NP完全問題
    • 不能將問題分成小問題杆故，需考慮各種可能情況，可能是NP完全問題
    • 如果問題涉及序列（e.g.旅行商問題中的城市序列）且難以解決溉愁，可能是NP完全問題
    • 如果問題涉及集合（e.g.廣播臺集合）且難以解決处铛，可能是NP完全問題
    • 如果問題可轉換為集合覆蓋問題或旅行商問題，肯定是NP完全問題

• 動態(tài)規(guī)劃：

  • 每個DP算法都從一個網格開始，單元格中的值通常就是你要優(yōu)化的值撤蟆，e.g.背包問題中奕塑，單元格值為物品價值。每個單元格都是一個子問題枫疆，應考慮如何將問題分解成子問題爵川，這有助于你找出網格的坐標軸。

  • 動態(tài)規(guī)劃可幫助你在給定約束條件下找到最優(yōu)解息楔。e.g.背包問題中寝贡，必須在背包容量給定的情況下，使得包含的物價總價值最高值依。

  • 背包問題：

    • 問題描述：一個人有一個可裝N磅的背包圃泡，可放的物品(共M件)對應不同的磅數(shù)和價值，為了讓總價值最高應該選擇那些物品愿险？
    • 背包問題的網格：維護一個二維表格（維）颇蜡，表格行為物品（M行），列為1~N不同容量的背包辆亏，不斷填充表格填滿后就找到問題的答案风秤。
    • 最優(yōu)子結構：前者即不放當前商品的價值
    • 明確最優(yōu)子結構后，當增加物品種類時扮叨，無需重新執(zhí)行之前所做的計算（DP逐步計算最大價值）缤弦，只需添加新行填充即可
    • 沿網格的一列往下走，最大價值可能降低嗎彻磁？不可能碍沐，每次迭代都存儲當前的最大價值，不可能比以前低
    • 行的排列順序發(fā)生變化時結果將如何衷蜓？不會累提，各行的排列順序無關緊要
    • 可以逐列而非逐行填充網格嗎？就這個問題而言不會磁浇，但對于其他問題可能有影響
    • 添加一件更小的商品會怎樣斋陪？最小單位從1磅變?yōu)?.5磅，需要重寫調整網格扯夭，考慮的粒度更細
    • 可以放商品的一部分嗎鳍贾？動態(tài)規(guī)劃（要么放，要么不放）無法處理這樣的問題交洗，可使用貪婪算法處理這種情況（盡可能多放價值最高的物品骑科，如果放完了，再盡可能放價值次高的物品...）

  • 旅游行程最優(yōu)化

    • 問題描述：你有一個列舉很多名勝所需的時間以及評分的清單构拳，假期兩天的話咆爽，能確定該去游覽哪些名勝嗎梁棠？
    • 分析：也是一個背包問題，約束條件不是背包的容量斗埂，而是有限的時間符糊，不是決定該裝入哪些物品而是決定該去游覽哪些名勝。
    • DP能夠解決子問題并使用這些答案解決大問題呛凶，僅當每個子問題都是離散的男娄，即不依賴其他子問題時。當子問題見互相依賴時漾稀，無法使用DP求解模闲。
    • 計算最終的解時會涉及兩個以上的子背包嗎？根據(jù)DP的設計最多只需合并兩個子背包崭捍，因此不會尸折，但這些子背包可能有包含子背包
    • 最優(yōu)解可能導致背包沒裝滿嗎？可能

  • 最長公共子串

    • DP中要將某個指標最大化殷蛇，給定兩個字符串实夹，判斷二者間的最長公共子串。網格中的值通常為要優(yōu)化的值粒梦，這里為兩個字符串都包含的最長子串的長度亮航，坐標軸為兩個單詞。如何將問題劃分為子問題呢匀们，即網格如何填充塞赂？

    • 沒有找出計算公式的簡單辦法，必須通過嘗試才能找到管用的公式昼蛀。

      if word_a[i] == word_b[j]:#兩個字母相同
          cell[i][j] = cell[i-1][j-1] + 1
      else:#兩個字母不同
          cell[i][j] = 0
      

      	V	I	S	T	A
      H	0	0	0	0	0
      I	0	1	0	0	0
      S	0	0	2（最終答案）	0	0
      H	0	0	0	0	0

    • 對于該問題最終答案不一定位于最后的單元格中（與上一個背包問題最終答案總在最后的單元格中不同）

  • 最長公共子序列

    • 兩個單詞中都有的序列包含的字母數(shù)，e.g.單詞fish和fosh

      if word_a[i] == word_b[j]:#兩個字母相同
          cell[i][j] = cell[i-1][j-1] + 1
      else:#兩個字母不同
          cell[i][j] = max(cell[i-1][j],cell[i][j-1])
      

      	F	O	S	H
      F	1	1	1	1
      I	1	1	1	1
      S	1	1	2	2
      H	1	1	2	3

  • 實際應用

    • 生物學家根據(jù)最長公共序列確定DNA鏈的相似性圆存，進而判斷兩種動物或疾病有多相似叼旋。最長公共序列還被用來尋找多發(fā)性硬化癥治療方案
    • 命令git diff用于指出兩個文件的差異，是使用DP實現(xiàn)的
    • 編輯距離指出了兩個字符串的相似程度沦辙，也是使用DP計算得到的夫植，編輯距離算法的用途很多，從拼寫檢查到判斷用戶上傳的資料是否是盜版油讯，都在其中详民。
    • Microsoft Word等具有斷字功能的應用程序，使用DP確定了在什么地方斷字以確保行長一致陌兑。

• K最近鄰算法

  • 一種機器學習分類算法（編組）沈跨，可用來構建推薦系統(tǒng)，e.g.Netflix為用戶創(chuàng)建一個電影推薦系統(tǒng)兔综，向Priyanka推薦電影饿凛，利用喜好相似（相似程度如何確定狞玛？）的用戶距離較近（Priyanka與最近的K個人，e.g. Justin, JC, Joey, Lance, Chris）涧窒，因此他們喜歡的電影可能Priyanka也喜歡心肪。

  • 相似程度如何確定？首先需要進行特征選取（即將樣本轉換為一系列可比較的數(shù)字）纠吴，e.g.如何判斷一個水果是橙子還是柚子硬鞍？可以根據(jù)顏色和個頭判斷，一般而言戴已，柚子更大更紅固该。對這個問題，個頭恭陡、紅的程度即問題的特征蹬音，每種水果用2個數(shù)字表示，根據(jù)特征將不同樣本放到圖表中休玩，轉化為一組坐標著淆，用于求解距離遠近。使用KNN時拴疤，挑選合適的特征很重要（與問題緊密相關的特征永部，且是不偏不倚的特征，e.g.只讓用戶給喜劇片打分呐矾，就無法判斷他們是否喜歡動作片）

  • 對電影推薦系統(tǒng)問題苔埋，將用戶放入圖表中，即可計算他們之間的距離了蜒犯。方法：用戶注冊是逻淌，要求他們指出對各種電影的喜歡程度。這樣小压，對每位用戶丁逝，都將獲得一組數(shù)字（構建圖表）,如下表：

    	Priyanka	Justin	Morpheus
    喜劇片	3	4	2
    動作片	4	3	5
    生活片	4	5	1
    恐怖片	1	1	3
    愛情片	4	5	1

    每位用戶都用5個數(shù)字表示。

  • 回歸：用于預測結果淘菩，e.g. 進一步預測Priyanka將給這部電影打多少分遵班，假設k=5，利用與其最近的5個人對該電影的評分預測Priyanka的打分潮改，e.g. Justin:5, JC:4, Joey:4, Lance:5, Chris:3狭郑，預測結果為打分的平均值4.2。

  • 余弦相似度：可用于計算兩位用戶的距離汇在，不計算兩個矢量的距離翰萨，而比較它們的角度。

  • OCR糕殉，光學字符識別缨历，google用來實現(xiàn)圖書數(shù)字化以蕴，使用KNN實現(xiàn)，通過瀏覽大量的圖像辛孵，將字的特征提取出來（訓練 training）丛肮，遇到新圖像時，提取該圖像的特征找出它最近的鄰居即可魄缚。一般而言宝与，OCR算法提取線段、點和曲線等特征冶匹。

  • 創(chuàng)建垃圾郵件過濾器：使用樸素貝葉斯分類器习劫，首先需使用一些數(shù)據(jù)對分類器進行訓練〗腊可研究句子中的每個單詞诽里，看它在垃圾郵件中出現(xiàn)的概率是多少。

• 二叉查找樹（binary search tree）

  • 對其中的每個節(jié)點飞蛹，左子節(jié)點的值都比它小谤狡，右子節(jié)點的值都比它大

    	數(shù)組	二叉查找樹
    查找
    插入
    刪除

  • 缺點：不能隨機訪問，處在不平衡狀態(tài)時卧檐，性能不佳

• 高級數(shù)據(jù)結構

  • 紅黑樹：處于平衡狀態(tài)的特殊二叉查找樹
  • B樹：一種特殊的二叉樹墓懂，數(shù)據(jù)庫常用它來存儲數(shù)據(jù)
  • 堆
  • 伸展樹

• 反向索引

  • inverted index，一種數(shù)據(jù)結構霉囚，通過構建散列表捕仔，鍵為單詞，值為包含指定單詞的頁面盈罐，將單詞映射到包含它的搜索頁面榜跌，常用于創(chuàng)建搜索引擎

• 傅里葉變換

  • 給定數(shù)字信號，傅里葉變換能夠將其中的各種頻率分離出來盅粪。因此斜做，可用于數(shù)字信號的壓縮、地震預測和DNA分析湾揽、音樂識別軟件

• 并行算法

  • 對數(shù)組進行排序是，快速排序的并行版本所需時間為
  • 可改善性能和可擴展性笼吟，但速度的提升是非線性的库物，即pc裝備了兩個而非一個內核，算法的速度也不可能提高一倍贷帮，原因：
    • 并行性管理開銷戚揭，e.g.對一個含1000個元素的數(shù)組排序，讓兩個內核每個內核對其中500個元素排序撵枢，再合并成一個有序數(shù)組民晒，合并也是需要時間的
    • 負載均衡：10個任務精居，給每個內核都分配5個，但給內核A的任務很容易潜必，10秒就完成了靴姿，而給內核B的任務很難，需要50秒完成磁滚，如何均勻分配工作讓兩個內核都一樣忙佛吓？

• MapReduce

  • 在并行算法只需2-4個內核時，完全可在筆記本上運行垂攘，但如果數(shù)百個內核维雇，可讓算法在多臺計算機上運行

  • 是一種分布式算法（一種特殊的并行算法），可通過Apache Hadoop來使用它

  • Map映射函數(shù)：接受一個數(shù)組晒他，對其中的每個元素執(zhí)行同樣的處理吱型。e.g. 你有一個URL清單，需要下載每個URL指向的頁面并將內容存儲在數(shù)組arr2中陨仅，當包含大量URL時津滞，執(zhí)行耗時很長。如果有100臺計算機掂名，map能夠自動將工作分配給這些計算機去完成据沈。

    >>> arr1 = # A list of URLs
    >>> arr2 = map(download_page, arr1)
    

  • reduce歸并函數(shù)：將很多項歸并為一項

    >>> arr1 = [1,2,3,4,5]
    >>> reduce(lambda x,y: x+y, arr1)
    15
    

  • MapReduce使用這兩個簡單概念在多臺計算機上執(zhí)行數(shù)據(jù)查詢，數(shù)據(jù)集很大（數(shù)十億行）使用MapReduce只需幾分鐘就可獲得查詢結果饺蔑，傳統(tǒng)數(shù)據(jù)庫可能要耗費數(shù)小時

• 布隆過濾器和HyperLogLog

  • 給定一個元素锌介，判斷它是否包含的這個集合中，為快速判斷可使用散列表猾警，但元素數(shù)量龐大（數(shù)萬億）時孔祸，散列表非常大，占用大量存儲空間发皿。
  • 布隆過濾器：一種概率性的算法/數(shù)據(jù)結構崔慧，它提供的答案有可能不對，但很可能是正確的穴墅。優(yōu)點：占用存儲空間少惶室，非常適合用于不要求答案絕對準確的情況。e.g.判斷網頁以前是否已搜集玄货，可不使用散列表（答案絕對可靠）而使用布隆過濾器皇钞。
    • 可能出現(xiàn)錯報的情況，即Google可能指出這個網站已搜集松捉，但實際上并沒有搜集
    • 不可能出現(xiàn)漏報的情況夹界，如果布隆過濾器說這個網站為搜集，就肯定未搜集
  • HyperLogLog：一種概率性的算法/數(shù)據(jù)結構隘世，Google要計算用戶執(zhí)行不同搜索的數(shù)量可柿，需要一個日志包含用戶執(zhí)行的不同搜索鸠踪，有用戶執(zhí)行搜索時，Google必須判斷該搜索是否包含在日志中复斥，如果不在必須將其加入到日志中营密。這樣會導致日志很大，而HyperLogLog近似計算集合中不同的元素數(shù)永票，它也不能給出準確答案卵贱，但很可能是正確的，而占用的內存空間卻少很多侣集。
  • 面臨海量數(shù)據(jù)且要求答案八九不離十時键俱，可考慮使用概率性算法

• SHA算法

  • 之前介紹的散列函數(shù)，用于確定將鍵關聯(lián)的值放到數(shù)組中世分，這里希望散列函數(shù)的結果是均勻分布的编振，用于創(chuàng)建散列表的散列函數(shù)接受一個字符串，返回一個索引號
  • SHA：另一種散列函數(shù)臭埋，安全散列算法（secure hash algorithm）,給定一個字符串踪央，SHA返回其散列值（一個很長的字符串）。SHA根據(jù)字符串生成另一個字符串瓢阴，對于每個不同的字符串畅蹂，SHA生成的散列值都不相同。
  • 可使用SHA判斷兩個文件是否相同荣恐，在比較超大型文件時很有用液斜，可計算它們的SHA散列值，再對結果進行比較
  • 還能在不知道原始字符串的情況下對其進行比較叠穆，e.g. Gmail攻擊者竊取了所有的密碼少漆，但你的密碼并未暴露，因為Google存儲的并非密碼硼被，而是密碼的SHA散列值示损。輸入密碼時，Google計算其散列值并將結果同其數(shù)據(jù)庫中的散列值進行比較嚷硫。這種散列算法是單向的检访，可根據(jù)字符串計算出散列值，但無法根據(jù)散列值推斷出原始字符串仔掸。
  • SHA是一個系列算法：SHA-0脆贵、SHA-1、SHA-2嘉汰、SHA-3 ，前兩者已被證明存在一些缺陷状勤，當前最安全的密碼散列函數(shù)是bcrypt
  • 是一個局部不敏感算法鞋怀，對字符串做微小修改得到的散列值將截然不同双泪，令攻擊者無法通過比較散列值是否類似來破解密碼

• 局部敏感的散列算法

  • Simhash算法，對字符串做細微修改密似，生成的散列值也只存在細微的差別焙矛，能夠通過比較散列值來判斷兩個字符串的相似程度。用于判斷網頁是否已搜集残腌，用于判斷學生論文是否是從網上抄的村斟、檢查上傳內容是否與某些有版權的內容類似（自動拒絕）

• Diffie-Hellman密鑰交換

  • 加密算法，一種雙方無需知道的加密算法抛猫，不必會面協(xié)商要使用的加密算法蟆盹，且破解加密的消息幾乎不可能。使用兩個密鑰：公鑰（公開的可發(fā)布闺金，有人要向你發(fā)送消息時逾滥，使用公鑰對其進行加密）和私鑰（加密后的消息只有使用私鑰才能解密，只有知道私鑰才能解密消息）败匹。
  • 替代算法RSA

• 線性規(guī)劃

  • 在給定約束條件下寨昙，最大限度的改善指定的指標。所有的圖算法都可使用線性規(guī)劃實現(xiàn)掀亩。
  • 使用Simplex算法