數(shù)據(jù)結(jié)構(gòu)是組織和訪問數(shù)據(jù)的一種系統(tǒng)化方式话速，算法是在有限的時間里一步步執(zhí)行某些任務的過程。
我們在本文中用到的主要分析方法包括算法和數(shù)據(jù)結(jié)構(gòu)的運行時間和空間利用表示耸三。

實驗研究

如果算法已經(jīng)實現(xiàn)了渊胸，我們可以通過在不同的輸入下執(zhí)行它并記錄每一次執(zhí)行所花費的時間來研究它的運行時間。Python中一個簡單的實現(xiàn)方法是使用time模塊的time()函數(shù)批幌。這個函數(shù)傳遞的是自新紀元基準時間后已經(jīng)過去的秒數(shù)或分數(shù)（新紀元是指1970年）。當我們可以通過記錄算法運行前的那一刻以及算法執(zhí)行完畢后的那一刻也嗓节，并且計算它們之間的差來判定消逝的時間時荧缘，新紀元的選擇不影響測試事件的結(jié)果。

7種函數(shù)

常數(shù)函數(shù)

f(n) = c
最基本的常數(shù)函數(shù)是g(n) = 1拦宣，注意：任何其他的函數(shù) f(n) = c都可以寫成常數(shù)c乘以g(n)截粗，即f(n)=cg(n)。

對數(shù)函數(shù)

數(shù)據(jù)結(jié)構(gòu)和算法分析中最令人感興趣的甚至驚奇的是無處不在的對數(shù)函數(shù)鸵隧，f(n)=log_bn绸罗，常數(shù)b>1。此函數(shù)定義如下：
x = log_bn 當且僅當b^x=n
按照定義豆瘫，log_b1=0珊蟀，b是對數(shù)的底數(shù)。
在計算機科學中靡羡，對數(shù)函數(shù)最常見的底數(shù)是2，因為計算機存儲整數(shù)采用二進制俊性，并且許多算法中的常用操作是反復把一個輸入分成兩半略步。事實上，這個底數(shù)相當常見定页，以至于當?shù)讛?shù)等于2時趟薄，我們通常會省略它的符號，即：logn = log₂n

線性函數(shù)

另一個簡單卻很重要的函數(shù)時線性函數(shù)典徊，
f(n)=n
即杭煎，給定輸入值n,線性函數(shù)f就是n本身恩够。
這個函數(shù)出現(xiàn)在我們必須對所有n個元素做基本操作的算法分析的任何時間。比如羡铲，比較數(shù)字x和大小為n的序列中的每一個元素蜂桶，需要做n次比較。

n log n函數(shù)

f(n) = n log n
對于一個輸入值n也切，這個函數(shù)是n倍的以2為底的n的對數(shù)扑媚。這個函數(shù)的增長速度比線性函數(shù)快，比二次函數(shù)慢雷恃。因此疆股，與運行時間是二次的算法相比較，我們更喜歡運行時間與n log n成比例的算法倒槐。我們會看到一些運行時間與n log n成比例的重要算法旬痹。例如：對n個任意數(shù)進行排序且運行時間與n log n成比例的最快可能算法。

二次函數(shù)

f(n) = n²
二次函數(shù)用在算法中的主要原因是讨越，許多算法中都有嵌套循環(huán)两残，其中內(nèi)存循環(huán)執(zhí)行一個線性操作數(shù)，外層循環(huán)則表示執(zhí)行線性操作數(shù)的次數(shù)谎痢。因此磕昼，在這個情況下，算法執(zhí)行了n*n = n²個操作节猿。

三次函數(shù)和其他多項式

f(n) = n³
這個函數(shù)在算法分析文章中出現(xiàn)的頻率較低票从，但它確實會時不時出現(xiàn)。

多項式

f(n)=a₀+a₁n+a₂n²+a₃n³+...+a_dn^d
例如滨嘱，下面所有函數(shù)都是多項式
1 f(n) = 2 + 5n + n²
2 f(n) = 1 + n²
3 f(n) = 1
4 f(n) = n
5 f(n) = n²

指數(shù)函數(shù)

f(n) = bⁿ
其中b是一個正的常數(shù)峰鄙，參數(shù)n是指數(shù)。在算法分析中太雨，指數(shù)函數(shù)最基本的情況是b=2吟榴。如果通過一個操作執(zhí)行一個循環(huán)，然后每次迭代所執(zhí)行的操作數(shù)目翻倍囊扳，則在第n次迭代所執(zhí)行的操作數(shù)目為2ⁿ吩翻。
從事計算工作的每個人都應該知道
1 + 2 + 4 +8 +...+ 2^n-1 = 2ⁿ -1

比較增長率

綜上所述，按順序給出的算法分析使用的7個常用函數(shù)如下圖所示：

理想情況下锥咸，我們希望數(shù)據(jù)結(jié)構(gòu)的操作時間與常數(shù)函數(shù)或者對數(shù)函數(shù)成正比狭瞎，而且我們希望算法以線性函數(shù)或nlogn函數(shù)來運行。運行時間為二次或者三次的算法不太實用搏予，除最小輸入規(guī)模的情況外熊锭，運行時間為指數(shù)的算法是不可行的。7個函數(shù)的增長率如下圖所示：

image.png

漸近分析

在算法分析中，我們重點研究運行時間的增長率碗殷，采用宏觀方法把運行時間視為輸入大小為n的函數(shù)精绎。例如：同行只要知道算法的運行時間按比例增長到n就足夠了。

大O符號

令f(n)和g(n)作為正實數(shù)映射正整數(shù)的函數(shù)锌妻。如果有實型常量c>0和整型常量n₀>=1滿足：
f(n) <= cg(n),當n>=n₀
我們就說f(n)是O(g(n))代乃。有時被說成"f(n)是g(n)的大O"
例如：函數(shù)8n+5是O(n)
使用大O符號描述運行時間
通過設定一些參數(shù)n，大O符號被廣泛用于描述運行時間和空間界限从祝。
命題：找最大數(shù)算法（即計算一系列數(shù)中的最大數(shù)）的運行時間為O(n)
大O符號的一些性質(zhì)
大O符號使得我們忽視常量因子和低階項襟己，轉(zhuǎn)而關(guān)注函數(shù)中影響增長的主要成分。
例如：
5n⁴ +3n³+2n²+4n+1是O(n⁴)
證明：注意牍陌，5n⁴ +3n³+2n²+4n+1<=（5+3+2+4+1)n⁴=cn⁴擎浴，令c=15，當n>=n₀=1時毒涧，即滿足題意贮预。
事實上，我們可以描述任何多項式函數(shù)的增長速率契讲。
如果f(n)是一個指數(shù)為d的多項式仿吞，即：f(n)=a₀+a₁n+a₂n²+a₃n³+...+a_dn^d
且a_d>0，則f(n)是0(n^d)捡偏。
因此唤冈，多項式中的最高階項決定了該多項式的漸進增長速率。