曉強Deep Learning的讀書分享會，先從這里開始，從大學(xué)開始。大家好，我是曉強，計算機科學(xué)與技術(shù)專業(yè)研究生在讀。我會不定時的更新我的文章，內(nèi)容可能包括深度學(xué)習(xí)入門知識，具體包括CV，NLP方向的基礎(chǔ)知識和學(xué)習(xí)的論文；網(wǎng)絡(luò)表征學(xué)習(xí)的相關(guān)論文解讀。當(dāng)然我每天的讀書心得也會分享給大家，可能涉及我們生活各個方面的書籍。我也會不定時回答大家的問題與大家一同進步，共同交流，互相監(jiān)督，結(jié)交更多的朋友。希望大家多留言，多交流，多多關(guān)照。我在這里等你一同學(xué)習(xí)，如果需要相關(guān)資料也可以私信我，進入我們的群大家庭。

【曉白】最近的更新有些少了，因為白天事情很多，沒有能夠騰出時間來寫文章。我注意到一個現(xiàn)象就是我回答關(guān)于CBA的問題閱讀量卻達到了幾千，但是不忘初心，牢記使命。我還是希望在這里分享一下技術(shù)文章。所以想一想有時間還是要整理寫一篇技術(shù)類文章啦，以對得起粉絲們對我的支持。以后我會不定期更文章，先從計算機視覺開始，逐步更新多個深度學(xué)習(xí)應(yīng)用領(lǐng)域的知識點，如有錯誤大家多指正，多交流，多討論，共同學(xué)習(xí)，互相進步。如果內(nèi)容對大家有一些幫助，請大家多點贊支持，分享。算法的設(shè)計與分析是程序員的基本功，所以我也會寫一些算法類的文章，供大家學(xué)習(xí)，討論。今天先從算法設(shè)計與分析的第一章開始。請關(guān)注我的文章鏈接，以后我會繼續(xù)更新，敬請期待。

算法定義：算法是解決某個問題的方法或過程，在整個計算機領(lǐng)域，算法無處不在！

(1) 操作系統(tǒng)的進程管理，內(nèi)存管理，……

(2) 編譯系統(tǒng)的語法分析、詞法分析、代碼優(yōu)化 …….

(3) 數(shù)據(jù)庫管理系統(tǒng)的數(shù)據(jù)操作算法、查詢優(yōu)化算法……

(4) Google、Baidu等搜索引擎使用PageRank算法……

(5) …….

主要更新內(nèi)容包括：設(shè)計算法及分析算法的理論、方法和技術(shù)；

可計算問題的算法設(shè)計與分析。

主要算法設(shè)計方法：

遞歸與分治策略

動態(tài)規(guī)劃

貪心算法

樹形搜索算法

近似算法

隨機算法

算法的分析方法：不同的設(shè)計方法有不同的分析方法 。

第一節(jié) 算法在計算機科學(xué)中的地位

算法是計算機科學(xué)的重要主題

70年代前

計算機科學(xué)基礎(chǔ)的主題沒有被清楚地認清

70年代

Knuth出版了《The Art of Computer Programming》

以算法研究為主線確立了算法為計算機科學(xué)基礎(chǔ)的重要主題

1974年獲得圖靈獎

70年代后

算法作為計算機科學(xué)核心推動了計算機科學(xué)技術(shù)飛速發(fā)展

計算機科學(xué)技術(shù)的體系：解決一個計算問題的過程

可計算理論：

計算模型

可計算問題/不可計算問題

計算模型的等價性--圖靈/Church命題

計算模型

計算模型是刻畫計算的抽象的形式系統(tǒng)或數(shù)學(xué)系統(tǒng)。在計算科學(xué)中，計算模型是指具有狀態(tài)轉(zhuǎn)換特征，能夠?qū)λ幚韺ο蟮臄?shù)據(jù)或信息進行表示、加工、變換和輸出的數(shù)學(xué)機器。

圖靈機是圖靈機理論中提出的理想模型，其可以實現(xiàn)任意復(fù)雜的計算。

英國數(shù)學(xué)家艾倫·圖靈在1936年提出了「圖靈機」的理論。「圖靈機」設(shè)想有一條無限長的紙條，紙條上有一個個方格，每個方格可以存儲一個符號，紙條可以向左或向右運動。

圖靈機可以做下面三個基本的操作：

1、讀取指針頭指向的符號。

2、修改方框中的字符。

3、將紙帶向左或向右移動，以便修改其臨 ，近方框的值。

用圖靈機完成異或操作。

嘗試將1 1 0做一個異或操作，即將1 1 0變成0 0 1。要圖靈機完成計算，就類似于向圖靈機輸入以下操作指令，這些指令組成了一個小程序。

圖靈機的意義：

思考：我有許多很復(fù)雜的公式需要計算，如果自己一個人算的話時間會很久。

思考：能不能有一個東西能幫我實現(xiàn)公式的計算，無論這個公式有多復(fù)雜？

思考：我能不能設(shè)計一個模型來證實這個實行是可行的？（數(shù)學(xué)家最喜歡建模型來證明了~）

思考：提出「圖靈機」理論，任何計算都可以簡化成固定的步驟，無論多復(fù)雜的計算都能實現(xiàn)了。

某些動手能力強的數(shù)學(xué)家利用電子工程學(xué)知識將許多真空管組成了一套設(shè)備，實現(xiàn)了「圖靈機」理論模型。隨著電子工程的不斷發(fā)展，原本龐大的計算機不斷變小，慢慢地變成了今天的計算機。

等價機器，除了圖靈機以外，人們還發(fā)明了很多其它的計算模型。包括：寄存器機

遞歸函數(shù)，λ演算，生命游戲，馬爾可夫算法。然而這些模型無一例外地都和圖靈機的計算能力等價，因此邱奇，圖靈和哥德爾提出了著名的邱奇-圖靈論題：一切直覺上能行可計算的函數(shù)都可用圖靈機計算，反之亦然。

通俗地說，停機問題就是判斷任意一個程序是否在有限的時間內(nèi)結(jié)束運行的問題。

程序簡單時容易做出判斷，當(dāng)例子復(fù)雜時會遇到較大的困難，而在某些情況下則無法預(yù)測。

可計算理論

計算模型

可計算問題/不可計算問題

計算模型的等價性--圖靈/Church命題

計算復(fù)雜性理論

在給定的計算模型下研究問題的復(fù)雜性

固有復(fù)雜性

復(fù)雜性下界

平均復(fù)雜性

復(fù)雜性問題的分類: P=NP?

公理復(fù)雜性理論

算法設(shè)計和分析

設(shè)計算法的理論、方法和技術(shù)

分析算法的理論、方法和技術(shù)

計算機軟件

系統(tǒng)軟件

工具軟件

應(yīng)用軟件

第二節(jié) 算法與程序

算法（Algorithm）的概念

通俗地講算法是指解決問題的一種方法或一個過程。

嚴格地講，算法是由若干條指令組成的有窮序列,且滿足下述性質(zhì)：

（1）輸入: 有零個或多個由外部提供的量作為算法輸入。

（2）輸出: 算法產(chǎn)生至少一個量作為輸出。

（3）確定性: 組成算法的每條指令是清晰的，無歧義的。

（4）有限性: 算法中每條指令的執(zhí)行次數(shù)是有限的， 執(zhí)行每條指令的時間也是有限的。

算法與程序的區(qū)別

程序是算法用某種程序設(shè)計語言的具體實現(xiàn)；

程序可以不滿足算法的性質(zhì)（4）----有限性。

例如:

操作系統(tǒng)，它是一個在無限循環(huán)中執(zhí)行的程序，因而不是算法。可把操作系統(tǒng)的各種任務(wù)看成是一些單獨的問題，每個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實現(xiàn)。

算法描述

描述算法可以有多種形式。可以用C/C++，python等編程語言或偽代碼描述算法。

第三節(jié) 算法復(fù)雜性分析

算法復(fù)雜性的含義

一個算法的復(fù)雜性的高低體現(xiàn)在運行該算法所需的計算機資源（主要指時間和空間資源）的多少上。

算法的復(fù)雜性主要分為:

時間復(fù)雜性

空間復(fù)雜性

算法的復(fù)雜性分析的用處途: 為求解一個問題選擇最佳算法、最佳設(shè)備

隨著計算機要解決的問題越來越復(fù)雜，規(guī)模越來越大，對求解這類問題的算法作復(fù)雜性分析具有特別重要的意義。

隨著計算機技術(shù)的迅速發(fā)展，對空間的要求往往不如對時間的要求那樣強烈。因此我們這里的分析主要強調(diào)時間復(fù)雜性的分析。

考慮時間復(fù)雜性的理由：

某些用戶需要提供程序運行時間的上限（用戶可接受的）；所開發(fā)的程序需要提供一個滿意的實時反應(yīng)。一般考慮最壞情況；最好情況；平均情況。

時間復(fù)雜性的計算方法(即估算運行時間的方法)： 加、減、乘、除、比較、賦值等操作，一般被看作是基本操作，并約定所用的時間都是一個單位時間；通過計算這些操作分別執(zhí)行了多少次來確定程序總的執(zhí)行步數(shù)。 一般地，一些關(guān)鍵操作執(zhí)行的次數(shù)決定了算法的時間復(fù)雜度。

例1：二分查找算法

template<class T>

int Max(T a[], int n)

{//尋找a[0:n-1]中的最大元素

int pos=0;

for (int i=1; i<n; i++)

if (a[pos]<a[i])

pos=i;

return pos;

}

例2：尋找最大元素：T(n)= O(n)

例3：非遞歸的折半搜索算法

while的每輪以減半的比例縮小搜索范圍，所以該循環(huán)在最壞的情況下需要執(zhí)行 O (log(n))次；每輪耗時 O(1) 。所以，T(n)=O(logn)。

例4：插入排序算法

排序算法對比算法：插入排序算法的時間復(fù)雜性是an2；歸并排序算法的時間復(fù)雜性是a’nlog2n；

計算機A: 109指令/秒, 計算機B: 107指令/秒

隨著輸入的規(guī)模增加，歸并排序要遠遠優(yōu)于插入排序

當(dāng)n=106時, A需要 ( 2(106)2指令)/(109指令/秒) = 2000秒

B需要 (50(106)log2106指令)/(107指令/秒)≈100秒

當(dāng)n=107時, A需要 2.3天

B需要 20分鐘

漸近復(fù)雜性分析： 確定程序的操作計數(shù)和執(zhí)行步數(shù)的目的是為了比較兩個完成同一功能的程序的時間復(fù)雜性，預(yù)測程序的運行時間隨著問題規(guī)模變化的變化量。

設(shè)T(n)是算法A的時間復(fù)雜性函數(shù)。 是算法A當(dāng)n→∞時的漸近時間復(fù)雜性，是T(n)中略去低階項所留下的主項。#T（n ） 進一步分析可知，漸近復(fù)雜性分析只要關(guān)心 #T（n ）的階就夠了，不必關(guān)心包含在 #T（n ） 中的常數(shù)因子。所以，我們還可對 #T（n ） 的分析進一步簡化。

綜上分析，我們已經(jīng)給出了簡化算法復(fù)雜性分析的方法和步驟，即只考慮當(dāng)問題的規(guī)模充分大時，算法復(fù)雜性在漸近意義下的階。為此引入漸近符號。在那之前，首先給出常用的漸近函數(shù)。

常用的階

第四節(jié) 計算復(fù)雜性函數(shù)的階

若用f(n)表示一個程序的時間或空間復(fù)雜性，則它是問題規(guī)模n的函數(shù)。由于程序的時間或空間需求是一個非負實數(shù)，即函數(shù)f(n)對于n (n≥0)的所有取值均為非負實數(shù)。

（1）高階函數(shù)記號

f(n)=O(g(n))當(dāng)且僅當(dāng)存在正的常數(shù)C和n0，使得對于所有的n≥n0，有f(n)≤ Cg(n)。此時，稱g(n)是f(n)的一個上界函數(shù)。

三點注意事項：（1）用來作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n)。

如：3n+2=O(n2) 松散的界限；

3n+2=O(n) 較好的界限。

（2）不要產(chǎn)生錯誤界限。

如: n2+100n+6

當(dāng)n<3時，n2+100n+6<106n，由此就認為n2+100n+6＝O(n)是錯誤的!

事實上，對任何正常數(shù)C，只要n>C-100就有n2+100n+6>C×n。

同理，3n2+4×2n=O(n2)是錯誤的界限。

（3）f(n)=O(g(n))不能寫成g(n)=O(f(n))。因為兩者并不等價。

（2）低階函數(shù)記號:

f(n)=Ω(g(n)) 當(dāng)且僅當(dāng)存在正的常數(shù)C和n0， 使得對于所有的n≥ n0 ，有f(n)≥C(g(n))。

此時，稱g(n)是 f(n)的下界

（3）同階函數(shù)記號:

設(shè)f(n)和g(n)是正值函數(shù)，f(n)=Θ(g(n))當(dāng)且僅當(dāng)存在正常數(shù)和C1，C2和n0，使得對于所有的n≥n0, 有C1(g(n))≤f(n)≤ C2(g(n))。此時，稱f(n)與g(n)同階

例： 3n+2= Θ(n)

5×2n +n2= Θ(2n)

（4）嚴格高階函數(shù)記號:

設(shè)f(n)和g(n)是正值函數(shù)。如果?c>0, 存在n0 , ?n>n0, f(n)<cg(n)，則稱f(n)嚴格比g(n)低階，或g(n)是f(n)的嚴格上界，記作f(n)=o(g(n))。

（5）嚴格低階函數(shù)記號:

設(shè)f(n)和g(n)是正值函數(shù)。如果?c>0, 存在n0 , ?n>n0, f(n)>cg(n)，則稱f(n)嚴格比g(n)高階，或g(n)是f(n)的嚴格下界函數(shù)，記作f(n)= ?(g(n))。

例： 3n2 +2= ? (n)

是否所有的函數(shù)之間都是可比的？

第五節(jié) 遞歸方程解的漸近階的求法三種求遞歸方程解的漸近階的方法：

(1)代入法（Substitution Method）

(2)迭代法 (Iteration Method)

(3)套用公式法（Master method）

（1）代入法（Substitution Method）

Substitution方法Ⅰ：聯(lián)想已知的T(n) ；

----Guess first, 然后用數(shù)學(xué)歸納法證明.

例1. 求解2T(n/2) + n

例2. 求解2T(n/2 + 17) + n

證明：用數(shù)學(xué)歸納法

Substitution方法II：上擠下壓

例2. 求解T(n) =2T(n/2)+n

Substitution方法III：變量替換----經(jīng)變量替換把遞歸方程變換為熟悉的方程.

(2)迭代法 (Iteration Method)

方法：

循環(huán)地展開遞歸方程， 把遞歸方程轉(zhuǎn)化為和式，然后可使用求和技術(shù)解之。

(3)套用公式法(Master method)

這個方法為估計形如T(n)=aT(n/b)+f(n)

的遞歸方程解的漸近階提供三個可套用的公式。

注：上式是一個遞歸方程，其中：a≥1和b>1是常數(shù)，f(n)是一個確定的正函數(shù)。

Master 定理：設(shè)a≥1和b>1是常數(shù)，f(n)是一個確定的正函數(shù)。T(n)是定義在非負集上的函數(shù)T(n)=aT(n/b)+f(n) .

T(n)可以如下求解：

直觀地說，可用f(n)與nlogba作比較：

（1）若 nlogba的階較大， 則T(n)=Θ(nlogba)。

（2）若 f(n)和nlogba同階 ，則T(n)=Θ(nlogbalogn) 。

（3）若f(n)的階較大， 則T(n)=Θ(f(n))。

例１： T(n)=9T(n/3)+n

此時，a=9,b=3,f(n)=n，

∴ nlogba ＝ nlog39＝ n2

可套用第一類情況得T(n)= Θ (n2)。

例2： T(n)=T(2n/3)+1

此時，a=1,b=3/2,f(n)=1，

∴ nlogba ＝ nlog3/21＝ n0=1

可套用第二類情況得T(n)= Θ (logn) 。

例３：T(n)=３T(n/４)+nlogn

此時，a=3,b=4,f(n)=nlogn，

∴nlogba ＝ nlog43＝ O(n0.793)

可套用第三類情況得T(n)= Θ (nlogn)。

例４： T(n)=２T(n/２)+nlogn

此時，a=２,b=２,f(n)=nlogn，

∴ nlogba ＝ nlog22＝n

此時f(n)在第二類情況和第三類情況的間隙 里，本方法對它無能為力。

注意：在第一類情況下， f(n)的階不僅必須比nlogba的階小，而且必須是多項式地比 nlogba的階小，即f(n)必須漸近地小于nlogba與n-ε的積，ε是某個正常數(shù)。

在第三類情況下， f(n)的階不僅必須比nlogba的階大，而且必須是多項式地比 nlogba的階大，即f(n)必須漸近地大于nlogba與n+ε的積，ε是某個正常數(shù)。

【曉議】今天技術(shù)文章更新完畢，算法設(shè)計與分析計算機基礎(chǔ)知識的第一篇。如果有需要繼續(xù)補充的，我會在后面繼續(xù)更新。每一部分的代碼講解，請關(guān)注我之后私信我，我會發(fā)給大家。您如果在計算機入門時或者想轉(zhuǎn)行學(xué)習(xí)計算專業(yè)的知識，有什么問題也可以一起討論解決。謝謝大家的關(guān)注和分享。如果對您有幫助，請幫我點贊，謝謝。附上之前的文章連接，方便大家學(xué)習(xí)。關(guān)注我，看更多更精彩的文章，我會按每天的進度安排，不定時更新對大家有益的內(nèi)容。

曉強DL：圖像處理必讀論文之AlexNet?zhuanlan.zhihu.com曉強DL：Opencv圖像處理(一)?zhuanlan.zhihu.com曉強DL：OpenCV圖像處理（二）?zhuanlan.zhihu.com曉強DL：Opencv圖像處理(三)?zhuanlan.zhihu.com曉強DL：Opencv圖像處理 （四）?zhuanlan.zhihu.com

總結(jié)

以上是生活随笔為你收集整理的哈工大威海算法设计与分析_计算机算法设计与分析第一章 算法概述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。