數(shù)據(jù)結(jié)構(gòu)與算法系列文章
數(shù)據(jù)結(jié)構(gòu)與算法 - 時(shí)間復(fù)雜度
數(shù)據(jù)結(jié)構(gòu)與算法 - 線性表
數(shù)據(jù)結(jié)構(gòu)與算法 - 樹形結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)與算法 - 查找
目錄
一、數(shù)據(jù)結(jié)構(gòu)概要
二、算法概要
三呐萨、時(shí)間復(fù)雜度簡(jiǎn)介
四、求解時(shí)間復(fù)雜度
一、數(shù)據(jù)結(jié)構(gòu)
? ? ? ?數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合谴分。在各類實(shí)際應(yīng)用問題中，數(shù)據(jù)元素之間總是存在著各種關(guān)系镀脂，描述數(shù)據(jù)元素之間關(guān)系的方法稱為結(jié)構(gòu)牺蹄。通常，可根據(jù)數(shù)據(jù)元素之間所存在的關(guān)系的不同特征薄翅，用4類基本結(jié)構(gòu)予以描述：
(1)集合：指結(jié)構(gòu)中的數(shù)據(jù)元素之間只存在“同屬一個(gè)集合”的關(guān)系沙兰。
間
(2)線性結(jié)構(gòu)：指結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一個(gè)對(duì)一個(gè)”的關(guān)系。
數(shù)
(3)樹形結(jié)構(gòu)：指結(jié)構(gòu)中的數(shù)據(jù)元素之間存在“一個(gè)對(duì)多個(gè)”的關(guān)系翘魄。
(4)圖形結(jié)構(gòu)：指結(jié)構(gòu)中的數(shù)據(jù)兀素之間存在“多個(gè)對(duì)多個(gè)”的關(guān)系鼎天。
二、算法
2.1熟丸、算法定義：
? ? ? ?通常训措，算法( Algorithm)是指解決問題的一種方法或一個(gè)過程。如果把問題看作函數(shù)，則算法就能把輸入轉(zhuǎn)化成輸出绩鸣。在數(shù)據(jù)結(jié)構(gòu)中导梆，算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列榴嗅。
? ? ? ?同一問題可以有多種不同的求解算法秤涩，一個(gè)給定的算法可以用來描述解決特定問題的一個(gè)具體的求解方案。了解對(duì)于同一問題的多種求解法有助于對(duì)算法的運(yùn)行效率進(jìn)行分析和比較捡多，加深對(duì)算法的理解蓖康。
2.2、算法設(shè)計(jì)：
? ? ? ?算法設(shè)計(jì)技術(shù)是用算法解題的一般性方法垒手，用于解決不同計(jì)算領(lǐng)域的多種問題蒜焊。常用的算法設(shè)計(jì)技術(shù)主要有蠻力法、分治法科贬、減治法泳梆、變治法、時(shí)空權(quán)衡榜掌、動(dòng)態(tài)規(guī)劃优妙、貪婪技術(shù)等。
1憎账、蠻力法
? ? ? ?蠻力法是一種簡(jiǎn)單直接地解決問題的方法套硼，常常直接基于問題的描述和所涉及的概念定義“澹可以應(yīng)用蠻力法解決廣闊領(lǐng)域的各種問題邪意，它是唯一一種幾乎什么問題都能解決的一般性方法。
2朴恳、分治法
? ? ? ?分治法將問題的實(shí)例劃分為若干個(gè)較小的實(shí)例抄罕，對(duì)這些較小實(shí)例遞歸求解，然后合并這些解于颖，以得到原始問題的解呆贿。
3、減治法
? ? ? ?減治法通過建立一個(gè)問題給定實(shí)例的解和同樣問題較小實(shí)例解的關(guān)系森渐，采用自頂向下(遞歸)或自底向上(非遞歸)的策略進(jìn)行求解做入。
? ? ? ?減治法有三個(gè)主要的變種：減一技術(shù)(每次迭代減去一個(gè)常量，通常為1)同衣、減半技術(shù)(每次選代減去一個(gè)常量因子竟块，通常為2)、減可變規(guī)模技術(shù)(每次選代規(guī)模減小的模式不同)耐齐。
4浪秘、變治法
? ? ? ?變治法基于變換的思想蒋情，將問題變換成更容易求解的形式。
? ? ? ?變治法有三個(gè)策略：實(shí)例化簡(jiǎn)(把問題的實(shí)例變換為相同問題的另一個(gè)實(shí)例耸携，使問題的求解更加容易)棵癣、改變表現(xiàn)(將一個(gè)問題實(shí)例的表現(xiàn)改變?yōu)橥瑯訉?shí)例的另一種表現(xiàn))、問題化簡(jiǎn)(把一個(gè)給定的問題變換成另一個(gè)可以用已知算法求解的問題)
5夺衍、時(shí)空權(quán)衡
? ? ? ?時(shí)空權(quán)衡主要有空間換時(shí)間和時(shí)間換空間兩種技術(shù)狈谊。在早期的計(jì)算機(jī)應(yīng)用中，硬件資源限制嚴(yán)重沟沙，許多問題包含的大量數(shù)據(jù)無法整體裝入計(jì)算機(jī)中一次處理河劝，需要通過時(shí)間換空間技術(shù)才能解決；但在硬件資源十分豐富的現(xiàn)在矛紫，算法設(shè)計(jì)通常采用空間換時(shí)間技術(shù)赎瞎。
? ? ? ?空間換時(shí)間技術(shù)有兩類，輸入增強(qiáng)技術(shù)颊咬，通過對(duì)問題輸入的部分或全部做預(yù)處理煎娇，以來提高算法的時(shí)間效率，加速問題的求解贪染；預(yù)構(gòu)造技術(shù)，通過使用額外的空間來實(shí)現(xiàn)更快或更方便的數(shù)據(jù)存取催享。
6杭隙、動(dòng)態(tài)規(guī)劃
? ? ? ?動(dòng)態(tài)規(guī)劃是一種對(duì)具有交疊子問題的問題進(jìn)行求解的技術(shù)。一般來說因妙，這樣的子問題出現(xiàn)在求解給定問題的遞推關(guān)系中痰憎，而該遞推關(guān)系包含了相同類型更小問題的解。它通過對(duì)每個(gè)較小的子問題求解一次并記錄在表中攀涵，從而避免對(duì)交疊子問題的重復(fù)求解铣耘，從表中得出原始問題的解。
7以故、貪婪技術(shù)
? ? ? ?貪婪技術(shù)通過一系列步驟來構(gòu)造問題的解蜗细，每一步對(duì)目前構(gòu)造的部分解做一個(gè)擴(kuò)展，直到獲得問題的完整解為止怒详。貪婪技術(shù)核心是炉媒，所做的每一步選擇都必須滿足可行、局部最優(yōu)和不可取消原則昆烁。
2.3吊骤、算法分析
? ? ? ?估量一個(gè)算法或計(jì)算機(jī)程序效率的方法，稱為算法分析静尼。所謂算法分析白粉，就是對(duì)一個(gè)算法所消耗的資源的估算传泊。算法分析的目的主要是考察算法的時(shí)間效率和空間需求，分別從算法的時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面進(jìn)行分析鸭巴，如果存在多個(gè)可行的算法眷细，則根據(jù)時(shí)間復(fù)雜度或空間復(fù)雜度這兩個(gè)指標(biāo)選取效率最高最優(yōu)的算法。
進(jìn)行算法分析需要了解的基本概念：
(1)問題規(guī)模：一般是指輸入量的數(shù)目奕扣。
(2)基本操作：通常是指具有完成該操作所需的時(shí)間與操作數(shù)的取值無關(guān)的性質(zhì)的操作薪鹦。
(3)代價(jià)：即實(shí)現(xiàn)一個(gè)算法所需的資源需求。
(4)增長(zhǎng)率：是指當(dāng)問題規(guī)模增大時(shí)惯豆，算法代價(jià)增長(zhǎng)的速率池磁。
(5)最佳、最差和平均代價(jià)：分別是指算法實(shí)現(xiàn)對(duì)資源需求的最小楷兽、最大和平均情況地熄。
三、時(shí)間復(fù)雜度
? ? ? ?算法的時(shí)間復(fù)雜度 是指算法對(duì)時(shí)間的需求芯杀。一個(gè)算法的運(yùn)行時(shí)間通常與所解決問題的規(guī)模大小有關(guān)端考。
? ? ? ?例如，在排序問題中揭厚，排序的元素個(gè)數(shù)n就是問題規(guī)模却特，排序算法中基本操作語句的重復(fù)執(zhí)行次數(shù)隨著問題規(guī)模n的增大而增加。
? ? ? ?一般情況下筛圆，算法中基本操作重復(fù)執(zhí)行的次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)裂明。因此，算法的時(shí)間效率可記為：T(n)= O(f(n))
表示隨問題規(guī)模n的增大太援，算法的執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同闽晦，稱作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度提岔。表達(dá)式中O的含義是指T(n)的數(shù)量級(jí)仙蛉。一般情況下，當(dāng)Tn)為多項(xiàng)式時(shí)碱蒙，可只取最高次冪項(xiàng)荠瘪，且系數(shù)也可省略。例如：T(n)=3n2+n-9 則T(n)=O(n2)赛惩。
? ? ? ?一般地巧还，算法所消耗的時(shí)間是每條語句的執(zhí)行時(shí)間之和。每條語句的執(zhí)行時(shí)間是其執(zhí)行次數(shù)(頻度)與該語句執(zhí)行一次所需時(shí)間的乘積坊秸。在計(jì)算機(jī)中麸祷，程序語句的執(zhí)行時(shí)間與計(jì)算機(jī)的性能有關(guān)，因此在分析算法的執(zhí)行效率時(shí)褒搔，假設(shè)語句執(zhí)行時(shí)間與機(jī)器無關(guān)阶牍，只考慮所有語句的執(zhí)行次數(shù)喷面。
? ? ? ?算法中的基本操作可以理解為算法程序中最深層循環(huán)內(nèi)的語句中的基本操作，它的執(zhí)行次數(shù)(頻度)與包含它的語句的執(zhí)行次數(shù)相同走孽。
? ? ? ?通常情況下惧辈，時(shí)間復(fù)雜度的表示以O(shè)(f(n))形式體現(xiàn)，如O(1)磕瓷、O(n)盒齿、O(n2)、O(log n)困食、O(2^n )等边翁。根據(jù)f(n)的具體形式，常稱某個(gè)算法的時(shí)間復(fù)雜度是常量階O(1)線性階O(n)硕盹、平方階O(n2)符匾、對(duì)數(shù)O(log n)、指數(shù)階O(2^n)等瘩例。常數(shù)階表示算法的時(shí)間復(fù)雜度與問題規(guī)模n無關(guān)啊胶。當(dāng)一個(gè)算法的時(shí)間復(fù)雜度體現(xiàn)為指數(shù)階時(shí)，通常將認(rèn)為不是一個(gè)有效的算法垛贤。
| T(n)與n的最高階數(shù)關(guān)系 | 名稱 |
|---|---|
| T(n)=O(1) | 常數(shù)階 |
| T(n)=O(n) | 線性階 |
| T(n)=O(n2) | 平方階 |
| T(n)=O(n3) | 立方階 |
| T(n)=O(2^n ) | 指數(shù)階 |
| T(n)=O(log n) | 對(duì)數(shù)階 |
| T(n)=O(n log n) | n log n階 |
? ? ? ? 空間復(fù)雜度是指算法執(zhí)行過程對(duì)計(jì)算機(jī)存儲(chǔ)空間的要求焰坪，稱為算法的空間復(fù)雜度。類似于時(shí)間復(fù)雜度聘惦，記為 S(n)= O(f(n)) 其中n是問題的規(guī)模琳彩。
? ? ? ?通常，執(zhí)行一個(gè)算法程序除了需要存儲(chǔ)空間存放本身所用的指令部凑、常數(shù)、變量和輸出數(shù)據(jù)外碧浊，還需要一些輔助空間用于對(duì)數(shù)據(jù)進(jìn)行處理及存儲(chǔ)處理過程中的中間信息涂邀。若輸入數(shù)據(jù)所占的空間只取決于問題本身而與算法無關(guān)，則只需要分析除了輸入和程序之外的輔助空間需求箱锐。算法的空間復(fù)雜度通常就是指這種輔助空間需求的大小比勉。
四、求解時(shí)間復(fù)雜度
最后通過實(shí)例來加深對(duì)時(shí)間復(fù)雜度的理解：
- 【例1】以下算法實(shí)現(xiàn)奇偶性判斷驹止，試分析時(shí)間復(fù)雜度浩聋。
int isOdd (int n) {
if(n % 2 == 0) { //(1)
return 1: //(2)
}else {
return 0; //(3)
}
}
分析：語句(1)執(zhí)行1次，根據(jù)表達(dá)式n%2==0結(jié)果臊恋，可能執(zhí)行語句(2)或語句(3)1次衣洁。
語句總執(zhí)行次數(shù)為T(n)=1+1=2
因此，算法的時(shí)間復(fù)雜度為常數(shù)階O(1)抖仅。算法的執(zhí)行時(shí)間與問題規(guī)模n無關(guān)坊夫。
- 【例2】遞歸算法實(shí)現(xiàn)求n砖第！，試分析時(shí)間復(fù)雜度环凿。
int func(int n) {
if(n <= 1) {
return 1; //(1)
}else {
return(n * func(n-1)); //(2)
}
}
分析：語句(1)的時(shí)間復(fù)雜度為O(1)梧兼，遞歸調(diào)用fact(n-1)的時(shí)間是T(n-1)，因此可得
當(dāng)n≤1時(shí)智听，T(n) = O(1)羽杰，
當(dāng)n>1時(shí):T(n) = T(n-1) + O(1)，T(n-1)=0(1)+T(n-2)到推，T(n-2)=O(1)+T(n-3）........
由此可推出
T(n)=(n-1)0(1)+T(1)=O(n)
因此遞歸求n考赛！算法的時(shí)間復(fù)雜度為O(n)。
推薦學(xué)習(xí)資料:
Swift從入門到精通
每周一道算法題
戀上數(shù)據(jù)結(jié)構(gòu)與算法（一）
戀上數(shù)據(jù)結(jié)構(gòu)與算法（二）
如果需要跟我交流的話：
※ Github： https://github.com/wsl2ls
※ 簡(jiǎn)書：http://www.reibang.com/u/e15d1f644bea
※ 微信公眾號(hào)：iOS2679114653
※ QQ：1685527540
