演算法入門——二分查找，旅行商問題，大O表示法
- 2020 年 3 月 6 日
- 筆記
一、 演算法入門
部落客在市面上發現了很多，很多有關書演算法的書籍，但是真正能夠讓初學者易懂的演算法書籍，只是一點點，以下我講以
Aditya Bhargava寫的一本關於演算法的入門書籍，為參考，這本書非常的優秀，淺顯易懂，圖文並茂！帶你走進演算法的世界，要知道，作為一名優秀的程式設計師，不會演算法是不行滴。
書籍的地址，可以給部落客留言，也可以加我QQ或者微信，歡迎你和我一起來探討，編程世界的秘密
二、 演算法簡介
所謂的演算法是一組完成任務的指令，這個任務可以是有關數學的，也可以是有關功能的實現，
演算法是電腦的靈魂
- 我們學習演算法可以幹些什麼呢？
具體說來，我們可以實現編寫跟著用戶的AI系統，編寫推薦系統，當然了還有NP的一些問題。不過呢，準備好掉頭髮了嗎？讓我們一起來掉頭髮吧！！第一個演算法——二分查找
所謂的二分查找演算法，是一個非常簡單的入門演算法，它的目的是加快數據的查找
1.讓我們從需求出發
- 我這裡現在有1~10的數子，我現在隨機說一個數組，你去猜。我們基本上可以使用兩種方法
- 一個一個的去猜，假如我說的1那麼恭喜你，你一下子就猜到了。要是我說的是10？那你可能要猜10次
- 使用二分查找法，假如我說的1那麼你可以猜5，我說」不對，大了「,那你又說」2」，我說「不對，大了」，如何你又猜到1，我說 「猜對了「這時候，你只需要猜3次就猜到了
- 在大量的數學論證中，我們可以用數學公式對二分查找所需要的最大次數，得出這樣的一個公式
[ x=log_2 N,2^3=8，log_28=3,log_22^3=3 ]
它指的是如果你在n個要查找的元素中，需要找一個元素，那麼你最多需要x步。
- 注意如果你連上述的公式都看不懂，那麼我也許會懷疑你的高數是不是體育老師教的了。
- 需要提醒你的是，這n個元素要有順序！，也就是說 如果是一個無序的組合，那麼這個演算法行不通
2. 如何用程式碼表示呢?（Python）
特別需要你注意的是：我們這選用python做為程式語言，python簡單易學
部落客比較忙，簡單的程式碼就不敲了，複雜一些的會帶著大家敲一下
三、對於演算法的效率
- 通過前面的學習，我們可能絕對這個二分查找好像並沒有多塊啊，但是如果你要查找40億個數據，使用二分查找你只需要35次
[ log_240(億)= 35 ]
[ log_2100 approx7 ]
那麼我們如何用另一種演算法來表示，它運算的時間呢？
難不倒我們偉大的程式設計師，這裡喲一種叫做大O表示法，一張圖告訴你
我們可以這樣子去理解，所謂的大O表示法，其實是 從演算法運算的時間增量的角度來衡量的，它沒有單位
例子1：比如下面的例子，有助於你的理解，
假設還是二分查找和普通的演算法，查找一次需要用到1毫秒ms，從n個中找一個元素，n=100時，普通演算法需要的時間是100ms，而二分查找需要的時間約等於7ms,當n=1000時，普通演算法是10s，二分查找需要耗費14ms， 有此我們可以使用以下的公式來表示，它們運行的速度 [ 普通演算法：O_(n), ]
[ 二分演算法：O_(log_2n) ]
我們這裡的（）括弧里的數表示的操作數，表示執行這個演算法需要操作多少步，或者說操作多少次。
例子2：現在有一個需求，在一張紙上面繪製16個各種，那麼如何用大O表示法，來觀察它的運行速度呢？
演算法1：一個一個的去畫，你需要畫16次， 演算法2：二分的去畫，只需要畫4次，這個4怎麼得來的呢？我們能不能用數學表示出來呢？當然可以，看我們的公式[ log_216=4 ]
所以在例子二中，演算法1，2用大O表示法就是
[ 普通演算法：O_(n), ]
[ 二分演算法：O_(log_2n) ]
再說一遍，我們的運行速度指是運算的時間的增量
1.我這裡指出了參加的大O運行時間
再來一個簡單的例子：
還是要繪製16個各種，如果現在要求繪製的1024的格子呢？我們如何用以上的5種表示法表示出來？
- 實際上，不可能如此乾淨的把大O運行時間轉化為操作數，就目前來看，這種情況下的精度就夠了，後面我們再來深入的套路大O表示法
2.總結一下
四.有趣的問題（旅行商的問題）
這是一個著名的電腦科學領域的問題，它充分的表示了最後一種大O表示法的運行速度
五、總結
- 二分查找的速度要快於簡單查找
[ 普通演算法：O_(n),比較慢，而且元素越多越慢 ]
[ 二分演算法：O_(log_2n) ]
- 演算法的運行時間不是s為單位，而是以其運算的增速角度來度量的
- 運算時間可以用大O來表示
