2017給自己列了幾項(xiàng)任務(wù)歪脏，其中之一就是重新學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)肮塞，從本文開始的一系列文章，都是自己研讀《數(shù)據(jù)結(jié)構(gòu)與算法分析 第二版》的學(xué)習(xí)心得铸本，其中一定會(huì)有偏頗甚至淺陋之處，隨時(shí)歡迎提出指正遵堵，謝謝箱玷！
基礎(chǔ)數(shù)學(xué)知識(shí)主要用到了指數(shù)、對(duì)數(shù)陌宿、級(jí)數(shù)以及證明方法锡足，內(nèi)容比較枯燥，我自己寫的也很痛苦壳坪，但這些知識(shí)總歸是有用的舶得，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法時(shí)也是必要的，所以自己還是硬著頭皮啃完了爽蝴。這其中好多公式都是高中的知識(shí)（理科）沐批，曾經(jīng)是信手拈來，現(xiàn)在好多公式和定理自己都在紙上推導(dǎo)了半天霜瘪，有些唏噓……好了，不廢話了惧磺，下面上干貨颖对，確實(shí)很干，干的嘴皮都破了……
用到的網(wǎng)站：<a herf:"http://www.codecogs.com/latex/eqneditor.php">數(shù)學(xué)公式編輯器</a>
一磨隘、指數(shù)
公式
-
?
-
?
-
?
- ?
 -
?
二缤底、對(duì)數(shù)
1.定義
如果X的A次冪為B顾患，則稱A為以X為底B的對(duì)數(shù)
在計(jì)算機(jī)科學(xué)中，如果沒有特別聲明个唧，則對(duì)數(shù)一般以2為底
2.定理
?
?
三江解、級(jí)數(shù)
公式
-
?
-
?
?
}{2}\approx \frac{N^{2}}{2})?
(2N+1)}{6}\approx \frac{N^{3}}{3})?
當(dāng)k=-1時(shí)，此公式不成立徙歼。此時(shí)我們需要下面的公式犁河，數(shù)Hn叫做調(diào)和數(shù)，這個(gè)和叫做調(diào)和和魄梯。這個(gè)近似式中的誤差趨向于0.57721566桨螺，被稱為歐拉常數(shù)γ。
四酿秸、模運(yùn)算
定義
如果N整除A-B灭翔，那么就說A與B模N同余，記為
)
直觀的看辣苏，就是說無論A還是B被N去除肝箱，所得余數(shù)都是相同的。翻譯一下：大家知道稀蟋，在數(shù)學(xué)中煌张，A/B被叫做：A被B除，或者B除A糊治。那么N整除A-B就意味著A%N = B%N唱矛，例如
)
五、證明方法
-
歸納法
由歸納法進(jìn)行的證明有兩個(gè)標(biāo)準(zhǔn)部分井辜。第一步是證明基準(zhǔn)情形绎谦，就是確定定理對(duì)于某個(gè)（某些）小的值的正確性；這一步幾乎總是很簡單粥脚。接著進(jìn)行歸納假設(shè)窃肠。一般來說，它指的是假設(shè)定理對(duì)直到某個(gè)有限數(shù)k的所有的情況都是成立的刷允。然后使用這個(gè)假設(shè)證明定理對(duì)下一個(gè)值（通常是k+1）也是成立的冤留。至此定理得證（在k是有限的情形下）
現(xiàn)在我們證明一下級(jí)數(shù)中的公式4
(2N+1)}{6}；N\geqslant 1)首先對(duì)于基準(zhǔn)情形树灶，我們?nèi)菀卓吹较伺?dāng)N=1時(shí)是成立的。然后假設(shè)定理對(duì)1<= k<=N成立天通，然后我們來證明該假設(shè)成立的情況下泊窘，對(duì)于N+1也是成立的。我們有
^2)
(2N+1)}{6}+(N+1)^2)
[\frac{N(2N+1)}{6}+(N+1)])
\frac{2N^2+7N+6}{6})
(N+2)(2N+3)}{6})
[(N+1)+1][2(N+1)+1]}{6})
定理得證
-
反例法
舉出一個(gè)反例即可。
-
反證法
反證法證明是通過假設(shè)定理不成立烘豹，然后證明該假設(shè)導(dǎo)致某個(gè)已知的性質(zhì)不成立瓜贾，從而原假設(shè)是錯(cuò)誤的。
一個(gè)經(jīng)典的例子是證明存在無窮多個(gè)素?cái)?shù)携悯。為了證明這個(gè)結(jié)論祭芦，我們假設(shè)定理不成立。于是憔鬼，存在某個(gè)最大的素?cái)?shù)Pk龟劲。令P1,P2,…,Pk是依次排列的所有素?cái)?shù)并考慮
顯然，N是比Pk大的數(shù)逊彭，根據(jù)假設(shè)N不是素?cái)?shù)咸灿，因?yàn)镻k是最大的素?cái)?shù)∥甓＃可是避矢，P1,P2,…,Pk都不能整除N，因?yàn)槌玫慕Y(jié)果總有余數(shù)1囊榜。這就產(chǎn)生一個(gè)矛盾审胸，因?yàn)槊恳粋€(gè)整數(shù)或者是素?cái)?shù)，或者是素?cái)?shù)的乘積卸勺。因此砂沛，Pk是最大素?cái)?shù)的原假設(shè)是不成立的，所以定理成立曙求。
