算法之?dāng)?shù)學(xué)

0x01 開坑：簡介

現(xiàn)今對數(shù)據(jù)處理的都是大量贩虾，大集合平道，所以簡介一些離散數(shù)學(xué)

例如：

問題一

設(shè)一組N哥數(shù)而要確定其中第K個最大者募强，我們稱之為選擇問題寞宫，只要學(xué)過編程的所以這種解決的“直觀方法”很多

方法一：比如冒泡萧福，遞減順序，然后返回位置K上的元素辈赋。

方法二：把K個元素讀入數(shù)組并遞減排序鲫忍，然后將剩下的元素再逐個讀入膏燕，當(dāng)新元素被讀到時，如果他小于數(shù)組的第K個元素則忽略悟民，否則將他放在數(shù)組中的正確位置坝辫，同時將原數(shù)組中的最后一個元素擠出數(shù)組。當(dāng)算法終止時射亏，位于第K個位置上的元素作為答案返回

這兩種都算法都非常簡單近忙，算法那個更好，或者是兩個算法夠好嗎智润？例如使用3000萬個元素的隨機文件和k=15000000進(jìn)行模擬指出银锻，兩個算法在合理的時間內(nèi)均不能結(jié)束計算；每種算法都需要計算機若干天才能算完(不過最終結(jié)果還是能夠算出來的).

問題二

解決字謎(word puzzle)游戲做鹰。輸入由一些字母構(gòu)成的二維數(shù)組和一個單詞表組成击纬。目標(biāo)是找出字謎中的所有單詞。如下表格

NULL	1	2	3	4
1	t	h	i	s
2	w	a	t	s
3	o	a	h	g
4	f	g	d	t

可以組成的單詞可以是 this,two,fat和that

現(xiàn)在有兩種算法可以滿足這個問題钾麸。

方法一：對單詞表中的每個單詞更振，我們檢查每個有序三元組(行，列饭尝，方向)肯腕，驗證是否有單詞的存在。這需要大量嵌套的for循環(huán)钥平，但他基本上是直觀的算法

方法二：對于每一個尚未越出迷板邊緣的有序四元組(行实撒，列，方向涉瘾，字符數(shù))知态，我們可以檢測是否所指的單詞再單詞表中。這也導(dǎo)致使用大量嵌套的for循環(huán)立叛。如果任意單詞中的最大字符數(shù)已知负敏，那么該算法有可能節(jié)省一些時間。

上述的兩種方法秘蛇，解決上面哪一種題還好解其做，如果要解決行列都有16個字符，上面就兩種算法就要花費相當(dāng)可觀的時間了赁还，但還是有方法能快速解決妖泄。

上述兩個問題都是都能簡單的體現(xiàn)在大量或大集合的運行時間問題，如果我們能夠估算程序的運行時間艘策，尤其是在蹈胡，如何在尚未編碼的情況下比較兩個程序的運行時間。我們還將顯著的節(jié)約成本，以及集中精力的優(yōu)化代碼段审残。

0x02 指數(shù)

$\frac{X^A}{X^b}=X^{A-B}$

$X^AX^B=X^{A+B}$

$(x^A)^B=X^{AB}$

$X^N+X^N=2X^N \neq X^{2N}$

$2^N+2^N=2^{N+1}$

0x03 對數(shù)

在計算機科學(xué)中梭域，除非有特別的聲明斑举，所有的對數(shù)都是以2為底的搅轿。

定義1

$X^A=B {當(dāng)且僅當(dāng)} log_xB=A$

定理1

$log_AB=\frac{log_CB}{logCA}; A,B,C>0 A \neq 1$

證明：

設(shè)
$X=log_CB， Y=log_CA富玷，Z=log_AB$
此時由對數(shù)定義
$C^X=B,C^Y=A,A^Z=B$
聯(lián)合上面三個則得到
$B=C^X=(C^Y)^Z \\ \Rightarrow X=YZ \\ \Rightarrow Z=X/Y$

定理2

$logAB=logA+logB; A,B>0$

證明：

方法同上
$X=logA璧坟， Y=logB，Z=logAB$
由定義得
$2^X=A,2^Y=B,2^Z=AB \\ \Rightarrow 2^X2^Y=2^{XY}$
下面的的公式都可以推導(dǎo)
$logA/B=logA-logB \\ log(A^b)=BlogA \\ logX<X 對所有的X>0成立 \\ log1=0,log2=1,log1024=10,log1048576=20$

0x04 級數(shù)

級數(shù)又分幾何級數(shù)和算數(shù)級數(shù)

幾何級數(shù):從第二項起,每一項是前一項的多少次方

算術(shù)級數(shù)：從第二項起赎懦，每一項均由前一項加一個常數(shù)所構(gòu)成的序列雀鹃。

幾何級數(shù)

常用的兩個公式為
$\sum_{i = 0} ^n 2^i=2^{N+1}-1 \quad (1) \\ \sum_{i = 0} ^n A^i=\frac{A^{N+1}-1}{A-1} \quad (2)$
其中公式2如果0<A<1則
$\sum_{i = 0} ^n A^i\leq\frac{1}{1-A}$
公式推導(dǎo)
$\sum_{i=0} ^\infty A^i(0<A<1)$
設(shè)S為總和
$S=1+A+A^2+A^3+A^4...... \\ 兩邊乘以A則 \\ AS=A+A^2+A^3+A^4+A^5...... \\ S-AS=1 \\ \Rightarrow S=\frac{1}{1-A}$
同樣的方法可以計算
$\sum_{i=1}^\infty i/2^i$

$S=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}...... \\ 兩邊同時乘以2 \\ 2S=1+\frac{2}{2}+\frac{3}{2^2}+\frac{4}{2^3}+\frac{5}{2^4}...... \\ 兩個相減 \\ 結(jié)果S=1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}$

算數(shù)級數(shù)

$\sum_{i=1}^ni=\frac{N(N+1)}{2}\thickapprox \frac{N^2}{2}$

例如：
$2+5+8+...+(3k-1)$
轉(zhuǎn)換成一
$3(1+2+3+...+k)-(1+1+1+1+...+1) \\ \Rightarrow \frac{3k(k+1)}{2-k}$
轉(zhuǎn)換成二
$第一項與最后一項的和都是3k+1 \\ 它有k/2的項，每一項和為 \\ S=\frac{k(3k+1)}{2}$

答案相同喲

但励两，現(xiàn)在下面說的兩個公式就不常見了
$\sum_{i=1}^Ni^2=\frac{N(N+1)(2N+1)}{6}\thickapprox \frac{N^3}{3} \\ \sum_{i=1}^Ni^k \thickapprox \frac{N^k+1}{|k+1|},k\neq-1$
當(dāng)K=-1時黎茎，公式2不成立。此時我們需要下面的公式当悔，這個公式在計算機科學(xué)中使用要遠(yuǎn)比在數(shù)學(xué)其他科學(xué)中用的頻繁傅瞻。
$H_N又稱調(diào)和數(shù)$
調(diào)和數(shù)的和又叫做調(diào)和和

下面近似中誤差趨向于
$\gamma \thickapprox0.57721566$
稱為歐拉常數(shù)
$H_N=\sum_{i=1}^N\frac{1}{i} \thickapprox log_eN$
一下兩個公式一般的代數(shù)運算：
$\sum_{i=1}^Nf(N)=Nf(N) \\ \sum_{i=n_0}^Nf(i)=\sum_{i=1}^Nf(i)-\sum_{i=1}^{n_0-1}f(i)$

0x05 模運算

如果N整除A-B，那么我們就說A與B模N同余盲憎，記為
$A\equiv B(mod N)$
無論A還是B被N除去嗅骄，所有余數(shù)都是相同的。類似
$81 \equiv 61 \equiv 1 (mod 10)$
如同等式的情形
$A \equiv B(mod N) \\ \Rightarrow A+C \equiv B+C(mod N) \\ 以及 AD \equiv BD(mod N)$
N常常為素數(shù)饼疙，對此溺森，我們有3個重要的定理：

定理一：

如果N是素數(shù)，那么
$ab \equiv 0 (modN) \\ \Rightarrow a\equiv 0 (mod N)\quad or \quad b \equiv0(modN)$

定理二：

如果N是素數(shù)
$ab \equiv 0 (modN) \\ \Rightarrow ax \equiv 1(mod N)對于所有的0<a<N \\ 有一個唯一的解（modN) \\ 這個解就是乘法逆元(multiplicative inverse) 其中滿x滿足:0<x<N$
定理三：

如果N是素數(shù)
$X^2 \equiv a (modN) 對于所有的 0<a<N \\ \Rightarrow 有兩個解或者沒有解$

0x06 證明方法

證明數(shù)據(jù)結(jié)構(gòu)分析結(jié)論的最常用的方法是歸納法和反證法(偶爾不得已也是用脅迫式證明（proof by intimidation)窑眯。證明一個定理不成立的最好方法是舉出一個反例

歸納法證明

歸納法進(jìn)行證明有兩個標(biāo)準(zhǔn)的部分

證明基準(zhǔn)情形（base case）
- 就是確定定理對于某個(某些)小的(通常是退化的)值的正確性
歸納假設(shè)(inductive hypothesis)
- 它指的是假設(shè)定理對直到某個有限數(shù)K的所有情況都是成立的屏积。然后使用這個假設(shè)證明定理對下一個值(通常是k+1)也是成立的至此定理得證(k是在有限的情況下)

舉例證明：斐波那契數(shù)列
$F_0=1,F_1=1,F_2=2,F_3=3,F_4=5,F_5=8........,F_i=F_{i-1}+F_{i-2} \\ 滿足對i\geq1 有F_i(5/3)^i。(有些規(guī)定F_0=0磅甩，這只不過將級數(shù)做一次平移)為了證明這個不等式 \\ 一:基準(zhǔn)情形 F_1=1 <5/3 ,F_2=2<25/9 得證 \\ 二:歸納假設(shè)定理對于i=1,2,3.....,k 成立肾请，證明定理正確就是歸納 \\ 為了證明定理,我們需要證明F_{K+1}=(5/3)^{K+1} \\ F_{k+1}=F_k+F_{k-1} 等號右邊 \\ \Rightarrow F_{k+1}<(5/3)^k+(5/3)^{k-1} \\ \quad \quad<(3/5)(5/3)^{k+1}+(3/5)^2(5/3)^{k+1} \\ \quad \quad<(3/5)(5/3)^{k+1}+(9/25)(5/3)^{k+1} \\ 化簡: F_{k+1}<(3/5+9/25)(5/3)^{k+1} \\ \quad \quad =(24/25)(5/3)^{k+1}<(5/3)^{k+1} \\ 得證$

定理：

$N \geq 1，則 \sum_{i=1}^Ni^2=\frac{N(N+1)(2N+1)}{6} \\ 證明：基準(zhǔn)情形 N=1時滿足,設(shè)\quad定理1\le k \le N成立 \\ \Rightarrow \sum_{i=1}^{N+1}i^2=\sum_{i=1}^{N}i^2+(N+1)^2 \\同理 \\右邊=（N+1）[\frac{N(2N+1)}{6}+(N+1)] \\ \Rightarrow（N+1）\frac{2N^2+7N+6}{6} \\ \Rightarrow \frac{(N+1)(N+2)(2N+3)}{6} \\ 得證 \sum_{i=1}^{N+1}i^2=\frac{(N+1)[(N+1)+1][2(N+1)+1]}{6}$

0x07 總結(jié)

已經(jīng)很久沒有復(fù)習(xí)數(shù)學(xué)了更胖，這一次復(fù)習(xí)已經(jīng)把很多數(shù)學(xué)知識撿起來了铛铁，心累。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末却妨，一起剝皮案震驚了整個濱河市饵逐，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌彪标，老刑警劉巖倍权，帶你破解...
沈念sama閱讀 211,265評論 6贊 490
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡薄声，警方通過查閱死者的電腦和手機当船，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,078評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來默辨，“玉大人德频，你說我怎么就攤上這事∷跣遥” “怎么了壹置？”我有些...
開封第一講書人閱讀 156,852評論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長表谊。經(jīng)常有香客問我钞护，道長，這世上最難降的妖魔是什么爆办？我笑而不...
開封第一講書人閱讀 56,408評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任难咕，我火速辦了婚禮，結(jié)果婚禮上距辆，老公的妹妹穿的比我還像新娘余佃。我一直安慰自己，他們只是感情好挑格，可當(dāng)我...
茶點故事閱讀 65,445評論 5贊 384
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布咙冗。她就那樣靜靜地躺著，像睡著了一般漂彤。火紅的嫁衣襯著肌膚如雪雾消。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,772評論 1贊 290
城市分裂傳說
那天挫望，我揣著相機與錄音立润，去河邊找鬼。笑死媳板，一個胖子當(dāng)著我的面吹牛桑腮，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播蛉幸，決...
沈念sama閱讀 38,921評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼破讨，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了奕纫？” 一聲冷哼從身側(cè)響起提陶，我...
開封第一講書人閱讀 37,688評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎匹层，沒想到半個月后隙笆，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,130評論 1贊 303
?護(hù)林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 36,467評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年撑柔，在試婚紗的時候發(fā)現(xiàn)自己被綠了瘸爽。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,617評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡铅忿，死狀恐怖剪决，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情辆沦，我是刑警寧澤昼捍，帶...
沈念sama閱讀 34,276評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布识虚，位于F島的核電站肢扯，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏担锤。R本人自食惡果不足惜蔚晨，卻給世界環(huán)境...
茶點故事閱讀 39,882評論 3贊 312
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望肛循。院中可真熱鬧铭腕，春花似錦、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,740評論 0贊 21
一樁弒父案届氢，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽可岂。三九已至，卻和暖如春昙啄，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 31,967評論 1贊 265
情欲美人皮
我被黑心中介騙來泰國打工只怎，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人怜俐。一個月前我還...
沈念sama閱讀 46,315評論 2贊 360
代替公主和親
正文我出身青樓身堡，卻偏偏與公主長得像，于是被迫代替她去往敵國和親拍鲤。傳聞我的和親對象是個殘疾皇子贴谎，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 43,486評論 2贊 348