一、 演算法入門
博主在市面上發現了很多，很多有關書演算法的書籍，但是真正能夠讓初學者易懂的演算法書籍，只是一點點，以下我講以
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來表示
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/77822.html
標籤：其他