算法心經：
??? 前幾天，一個好友告訴我，他要寫一本書，叫《編程低手箴言》，我馬上管他要地址去看看，出乎意料，寫得比我想象得好。后來我就自己在想，是不是也應該把我平時的一些心得寫出來呢？越越沖動，既然有了想法，那內容選什么呢？既然講給別人聽，就要拿自己拿手的，也就是最有把握的，要不一貼出來被人們拍死就麻煩了。所以，我把題材選為了講算法，名字嘛，就姑且叫《算法心經》好了。
?? 寫出點東西，勇氣是必不可少的，像CSDN有個知名作者，寫過一個什么關于矩陣的新見解，馬上被無數潛水的高手們拍得半死，其實我一看很多的批評也沒什么道理，即使有道理的也糾纏在名字這種taste differ的范圍內，不過因為缺少勇氣，他再也不出這個矩陣的續篇了。我就不同，也許差點水平，但絕不差勇氣。寫這個東東除了給別人看外，也是對自己平時遇到的一些很有意思的問題的總結，如果大家發現了什么不妥，請馬上幫我指出來。
?? 講算法的資料太多了，大多老一套，貪婪、分枝、限界等，如果想按這個套路學，那大家都去看MIT的算法導論好了，我再寫出來也是copy。既然是原創，就要有點新意，下面的內容完全按我對各種算法的思路總結來整理，保證您看著一個與眾不同。另外介于本人的水平有限，所有例子只對我碰上讀過的感覺有用的問題舉例，嫌不夠深入的朋友抱歉。
??? 廢話少說，開始...

一，數學的應用：
??? 我在抱本數學書看時，經常有同學問我，“看這玩意干啥子？“我答曰：”有用“，又問：“有啥用”，我托腮沉思半天，只擠出“反正有用”這種教條結論。的確，地球人都知道數學和計算機關系曖昧，但具體到哪有交集，又說不清楚，我看可能有兩個原因：1，還不到能理解到數學用處的水平。2，使數學后，沒有歸納總結。我想大多數人屬于后者，為了彌補這點，我把平時用到數學的地方總結出來，讓大家看看數學的威力。

積分的應用
??? 微積分是高等數學的基礎，但我們搞程序的平時使到微積分的時候實在少之又少，反正我大四以前根本沒有用到微積分（編寫什么插值求積分那種程序不算），果真如此嗎？？？
??? 微積分的威力發揮在算法分析上，你會算法分析嗎？會的話，肯定會體會到。看看積分的例子：
??? “有一個無序數列，每次遍歷整個數列查找一個數，然后刪除之，重復這個步驟直到數列為空，問這個算法的效率？”
??? 這個你一眼就看出效率了，遍歷的次數從1個增加到n個，那么平均是n/2個，一共執行n次，所以效率是n*n/2，也就是O(n*n)，呵呵，很簡單，愜意的笑。但細想一想，為什么這里能把n除以2呢？是因為n是個線性函數，所以在計算時可以用它的中間值來計算。這種中間值概念的應用很普遍，很多算法效率的計算有需要，回憶在quick sort的效率分析里，因為整個數列里的每個數與第一個數（比較數）交換的概率相同，那就是絕對的線性關系（函數為常數），所以才可以用，2*T(k)代替T(k)+T(n-k)。

??? 其實這題也可以用積分來算，效率實際上就是把n在1到n上取積分，也就是n*n/2，和先前的答案一樣，注意這里，積分本身是一個連續的數學概念，這里擴展到離散求積分。
??? 我們把上面的例子改改：
??? “有一個有序數列，每次用二分查找找到其中一個值，刪除之，重復這個步驟直到數列為空，問這個算法的效率？“
??? 想啊想啊，二分效率是log(n)，從log(n)降到log(1)，那么和先前的一樣，效率是中間值*n，就是log(n)/2*n，也就是O(n*log(n))，我趕緊握著你的手說，“恭喜你，蒙對了！”，最終的答案確實是O(n*log(n))，但絕不是這么出來的，因為log函數不是線性函數，你絕對不能用中間值代替來進行計算。
??? 哦！那該怎么計算呢？積分來了。上面的算法實際是對log操作從1增加到n，在數學上實際是離散的對log函數做1到n的積分，也就是對log(n)積分。那log(n)的積分怎么算呢？用Udi的《算法導引》的估計法，我們先估計其積分是n*n，我們對n*n求導
??? D(n*n)=2*n>log(n)
??? 我們的估計大了，那么是不是n*log(n)呢？
??? D(n*log(n)) = D(n)*log(n) + n*D(log(n)) = log(n)+ n*1/n=log(n) +1
??? 哇！我們對了，n*log(n)求導就是log(n)再和一個常數相加，于是可以判斷log(n)的積分就是和n*log(n)一個等級的，于是，答案出來了，這個算法的效率是n*log(n)，這就是積分的威力。

??? 下節我們來看微分的應用...

轉自：http://hi.baidu.com/jrckkyy/blog/item/d1c1c00e0ed39ac07acbe16a.html

總結

以上是生活随笔為你收集整理的算法心经.数学的应用.积分的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。