第一章緒論

本系列讀書筆記參考自數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)典問題解析第二版內(nèi)容，習(xí)題答案部分有誤，已勘正塘安，部分嚴(yán)格證明參考算法導(dǎo)論第三版，水平有限援奢，如有紕漏兼犯，盡請指出

基礎(chǔ)概念

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲和組織數(shù)據(jù)的一種特定方式，通過特定的數(shù)據(jù)結(jié)構(gòu)可以使相應(yīng)的數(shù)據(jù)處理更加有效集漾，常見的數(shù)據(jù)結(jié)構(gòu)包括：數(shù)組切黔，文件，鏈表具篇，棧纬霞，隊(duì)列，樹驱显，圖等诗芜。

根據(jù)其元素組織方式，數(shù)據(jù)結(jié)構(gòu)可分為兩種類型：

線性數(shù)據(jù)結(jié)構(gòu)：可以按線性次序訪問元素埃疫，但它并不強(qiáng)制將所有元素連續(xù)存儲在一起（如鏈表）伏恐。主要有鏈表，棧和隊(duì)列
非線性數(shù)據(jù)結(jié)構(gòu)：這種數(shù)據(jù)結(jié)構(gòu)的元素是以非線性次序來存儲和訪問元素的熔恢，例如樹和圖

為了簡化求解問題的過程脐湾，我們將數(shù)據(jù)結(jié)構(gòu)和相關(guān)運(yùn)算組合起來臭笆，統(tǒng)稱為抽象數(shù)據(jù)類型ADT叙淌，其包含兩個(gè)部分：數(shù)據(jù)的聲明和運(yùn)算的聲明
常用的ADT包括：鏈表秤掌，棧，隊(duì)列鹰霍，優(yōu)先隊(duì)列闻鉴，二叉樹，字典茂洒，并查集孟岛，散列表，圖等其他類型

當(dāng)定義ADT時(shí)督勺，不需要考慮其實(shí)現(xiàn)細(xì)節(jié)渠羞，僅當(dāng)需要使用它們時(shí)，才考慮具體的實(shí)現(xiàn)智哀。不同的ADT類型適用于不同的場合次询，需要我們靈活應(yīng)用

算法分析的目標(biāo)在于根據(jù)運(yùn)行時(shí)間及其它的一些因素（如內(nèi)存，開發(fā)者的工作量等）來比較算法的優(yōu)劣
運(yùn)行時(shí)間分析是指當(dāng)問題的輸入規(guī)模增大時(shí)瓷叫，研究問題的處理時(shí)間是如何增加的

為了比較算法屯吊，以下是幾種客觀評價(jià)指標(biāo)：

執(zhí)行時(shí)間：不同的計(jì)算機(jī)會呈現(xiàn)出較大差異，不是一個(gè)好的評價(jià)標(biāo)準(zhǔn)
執(zhí)行的語句數(shù)：因?yàn)閳?zhí)行的語句和編程語言以及程序員個(gè)人的編程風(fēng)格相關(guān)摹菠，也不是一個(gè)好的評價(jià)標(biāo)準(zhǔn)
函數(shù)表示：假設(shè)用一個(gè)函數(shù) $f(n)$ 表示一個(gè)算法的運(yùn)行時(shí)間盒卸，而問題的輸入規(guī)模用 $n$ 表示，通過比較不同算法對應(yīng)的的 $f(n)$ 次氨，就足以比較出各種算法的優(yōu)劣

增長率是指隨著輸入規(guī)模的增加蔽介，算法運(yùn)行時(shí)間增加的速度，也就是說對于一個(gè)給定的函數(shù)煮寡，我們會忽略相對影響更小的低階因變量（當(dāng)n很大時(shí)）屉佳，例如對于下式我們可以認(rèn)為：
$n^4+2n^2+100n+500\approx n^4$

image.png

算法分析

算法分析有如下三種類型：

最壞情況：定義算法最長運(yùn)行時(shí)間的輸入，這種輸入使得算法運(yùn)行最慢
最好情況：定義算法最短運(yùn)行時(shí)間的輸入洲押，這種輸入使得算法運(yùn)行最快
平均情況：提供算法運(yùn)行時(shí)間的預(yù)測值武花，此時(shí)假設(shè)輸入是隨機(jī)的，也就是說有：
$下界\leq 平均時(shí)間\leq 上界$

在我們定義了輸入的不同類型后杈帐，我們需要對算法運(yùn)行時(shí)間的上下界和平均時(shí)間做一個(gè)準(zhǔn)確的定義

大O表示法

大O表示法給出了函數(shù) $f(n)$ 的嚴(yán)格上界体箕，我們記作 $f(n)=O(g(n))$ ，表示當(dāng)輸入規(guī)模 $n$ 很大時(shí)挑童， $f(n)$ 的漸進(jìn)上界是 $g(n)$

用更準(zhǔn)確的數(shù)學(xué)語言來說累铅，大O表示法定義為：
$O(g(n))=\{f(n):存在正常數(shù)c和n_0，使得對任意n\geq n_0,0\leq f(n)\leq cg(n)成立\}$

注意當(dāng)邊界只能大于（小于）而不能等于時(shí)站叼，認(rèn)為邊界是漸進(jìn)的但不是緊確的娃兽，也就是滿足下式
$o(g(n))=\{f(n):存在正常數(shù)c和n_0，使得對任意n\geq n_0,0\leq f(n)< cg(n)成立\}$
此時(shí)我們稱 $g(n)$ 是 $f(n)$ 的一個(gè)漸進(jìn)非緊確上界

顯然 $O(g(n))$ 是指所有與 $g(n)$ 具有相同增長率或比起增長率小的函數(shù)的集合尽楔，例如下圖

image.png

但使用小o表示法投储，則不包含例如內(nèi)的函數(shù)

$\Omega$ 表示法

與大O表示法類似第练， $\Omega$ 表示法給出 $f(n)$ 的嚴(yán)格下界，記作 $f(n)=\Omega (g(n))$ 玛荞，表示輸入規(guī)模 $n$ 很大時(shí)娇掏， $f(n)$ 的漸進(jìn)下界是 $g(n)$

用更準(zhǔn)確的數(shù)學(xué)語言來說， $\Omega$ 表示法定義為：
$\Omega(g(n))=\{f(n):存在正常數(shù)c和n_0勋眯，使得對任意n\geq n_0,0\leq cg(n)\leq f(n)成立\}$

在使用中婴梧，我們需要盡可能求出滿足條件的最大階的 $g(n)$

同樣的當(dāng)滿足下式
$\omega(g(n))=\{f(n):存在正常數(shù)c和n_0，使得對任意n\geq n_0,0\leq cg(n)< f(n)成立\}$

此時(shí)我們稱 $g(n)$ 是 $f(n)$ 的一個(gè)漸進(jìn)非緊確下界

例如 $f(n)=n^2+2n$ 客蹋，則 $f(n)=\omega(n)塞蹭，f(n)=\Omega(n)$ 是正確的，而 $f(n)=\Omega(n^2)$ 也是正確的讶坯， $f(n)=\omega(n^2)$ 是錯(cuò)誤的

$\Theta$ 表示法

$\Theta$ 表示法決定了算法的時(shí)間增長率上界和下界是否相同浮还，如果大O表示法與 $\Omega$ 表示法給出的結(jié)果是一樣的，那么 $\Theta$ 表示法也會給出相同的結(jié)果闽巩。而對于一個(gè)給定的函數(shù)钧舌，如果它增長率的上界和下界是不同的，那么 $\Theta$ 表示法需要通過分析所有可能的時(shí)間復(fù)雜度涎跨，然后得出平均情況下的結(jié)論（例如快速排序的平均情況洼冻，參見第十章）

$\Theta$ 表示法的數(shù)學(xué)含義：

對于函數(shù) $f(n),g(n)$ ，如果存在常數(shù) $c(c>0)$ 使得 $\lim_{n\to \infty}\frac{f(n)}{g(n)}=c$ 隅很，那么有 $f(n)=\Theta (g(n))$
$\Theta(g(n))=\{f(n):存在正常數(shù)c_1,c_2和n_0撞牢，使得對任意n\geq n_0,0\leq c_1g(n)\leq f(n)\leq c_2g(n) 成立\}$

用圖示表示以上表示法如下：

image.png

小結(jié)：

image.png

一些通用的計(jì)算規(guī)則：

image.png

漸進(jìn)表示法的基本性質(zhì)：

image.png

一些常用的數(shù)學(xué)公式：

image.png

分治法定理

分治法是指把一個(gè)問題劃分為多個(gè)子問題，每個(gè)子問題是原問題的一部分叔营，然后執(zhí)行一些額外的工作來計(jì)算最后的答案屋彪，例如歸并排序中，將原問題分為兩個(gè)子問題绒尊，每個(gè)子問題都是原問題規(guī)模的一半畜挥，然后用 $O(n)$ 的額外工作完成歸并，可以用下式表示
$T(n)=2T(\frac{n}{2})+O(n)$

我們把這種分治法思想推廣婴谱，如果一個(gè)問題可以通過以下遞歸形式表示
$T(n)=aT(\frac{n}蟹但)+\Theta(n^k\log^pn),a\geq 1,b>1,k\geq 0$
則有如下幾種情況：

當(dāng) $a>b^k$ 時(shí)， $T(n)=\Theta(n^{\log_b^a})$
當(dāng) $a=b^k$ 時(shí)
a. 如果 $p>-1$ 谭羔， $T(n)=\Theta(n^{\log_b^a}\log^{p+1}n)$
b. 如果 $p=-1$ 华糖， $T(n)=\Theta(n^{\log_b^a}\log\log n)$
c. 如果 $p<-1$ ， $T(n)=\Theta(n^{\log_b^a})$
如果 $a<b^k$
a. 如果 $p\geq 0$ 瘟裸， $T(n)=\Theta(n^{k}\log^{p}n)$
b. 如果 $p<0$ 客叉， $T(n)=\Theta(n^k)$

這就是分治法的主定理，下面是一些使用主定理的例子

image.png

在主定理之上，還有一些變形：

變形1：當(dāng)對于常數(shù) $c,a>0,b>0,k\geq 0$ 和 $f(n),T(n)$ 有
$T(n)=\begin{cases}c&&n\leq 1\\ aT(n-b)+f(n)&&n>1 \end{cases}$
如果 $f(n)$ 的時(shí)間復(fù)雜度是 $O(n^k)$ 兼搏，則
$T(n)=\begin{cases}O(n^k)&&a<1\\ O(n^{k+1})&&a=1\\ O(n^{k}a^{\frac{n}卵慰})&&a>1 \end{cases}$

變形2： $T(n)=T(\alpha n)+T((1-\alpha)n)+\beta n,0<\alpha <1,\beta>0$ ，則其復(fù)雜度為 $O(n\log n)$

猜測的方法

image.png

平攤分析

image.png

下面是一些典型習(xí)題及其解答

image.png

上圖中F(2)還需要分為F(1)和F(0)向族，樹有N層

image.png

解答有誤，應(yīng)該是假設(shè)是一顆滿二叉樹棠绘，則葉子節(jié)點(diǎn)少于 $2^n$ (事實(shí)上件相，依然屬于 $2^n$ 階)

時(shí)間復(fù)雜度： $O(2^n)$
空間復(fù)雜度： $O(n)$

image.png

也就是說 $T(n)=n+\frac{n}{2}+\frac{n}{3}+\cdots+\frac{n}{n}=\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac{1}{i}=n\log n$

image.png

上式中注意省略掉這一步

image.png

最后編輯于：2019.09.29 14:23:31

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市氧苍，隨后出現(xiàn)的幾起案子夜矗，更是在濱河造成了極大的恐慌，老刑警劉巖让虐，帶你破解...
沈念sama閱讀 221,820評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件紊撕，死亡現(xiàn)場離奇詭異玫镐，居然都是意外死亡捍岳，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,648評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門菜谣，熙熙樓的掌柜王于貴愁眉苦臉地迎上來惭缰，“玉大人浪南，你說我怎么就攤上這事∈埽” “怎么了络凿？”我有些...
開封第一講書人閱讀 168,324評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長昂羡。經(jīng)常有香客問我絮记，道長，這世上最難降的妖魔是什么虐先？我笑而不...
開封第一講書人閱讀 59,714評論 1贊 297
?港島之戀（遺憾婚禮）
正文為了忘掉前任怨愤，我火速辦了婚禮，結(jié)果婚禮上蛹批，老公的妹妹穿的比我還像新娘憔四。我一直安慰自己，他們只是感情好般眉，可當(dāng)我...
茶點(diǎn)故事閱讀 68,724評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布了赵。她就那樣靜靜地躺著，像睡著了一般甸赃。火紅的嫁衣襯著肌膚如雪柿汛。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,328評論 1贊 310
城市分裂傳說
那天，我揣著相機(jī)與錄音络断，去河邊找鬼裁替。笑死，一個(gè)胖子當(dāng)著我的面吹牛貌笨，可吹牛的內(nèi)容都是我干的弱判。我是一名探鬼主播，決...
沈念sama閱讀 40,897評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼锥惋，長吁一口氣：“原來是場噩夢啊……” “哼昌腰！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起膀跌，我...
開封第一講書人閱讀 39,804評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤遭商，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后捅伤，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體劫流，經(jīng)...
沈念sama閱讀 46,345評論 1贊 318
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,431評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年丛忆，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了祠汇。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,561評論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡熄诡，死狀恐怖座哩，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情粮彤，我是刑警寧澤根穷，帶...
沈念sama閱讀 36,238評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站导坟，受9級特大地震影響屿良，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜惫周，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,928評論 3贊 334
男人毒藥：我在死后第九天來索命
文/蒙蒙一尘惧、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧递递，春花似錦喷橙、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,417評論 0贊 24
一樁弒父案贰逾，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至菠秒，卻和暖如春疙剑，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,528評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工言缤，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留嚼蚀，地道東北人。一個(gè)月前我還...
沈念sama閱讀 48,983評論 3贊 376
代替公主和親
正文我出身青樓管挟，卻偏偏與公主長得像轿曙，于是被迫代替她去往敵國和親。傳聞我的和親對象是個(gè)殘疾皇子僻孝，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,573評論 2贊 359

第一章 緒論

基礎(chǔ)概念

算法分析

分治法定理

推薦閱讀更多精彩內(nèi)容

第一章緒論