算法
● 確定性
可以描述為一個(gè)由基本操作組成的序列
● 可行性
每一基本操作都可實(shí)現(xiàn)，且在常數(shù)時(shí)間內(nèi)完成
● 有窮性
大 O 記號(hào)
T(n) = O(f(n)) iff 存在 c>0，當(dāng) n>>2 時(shí)，有 T(n)<c*f(n)
- 常數(shù) : O(1)
對(duì)數(shù) : O(logn)
多項(xiàng)式 : O(n^c) [ 線性 ]
指數(shù) : O(a^n) [ 任意 c >1，n^c = O(2^n) ]
級(jí)數(shù)
算數(shù)級(jí)數(shù)：與末項(xiàng)平方同階
T(n) = 1 + 2 + 3 + … + n = n(n+1)/2 = O(n^2)冪方級(jí)數(shù)：比冪次高出一階
T2(n) = 1^2 + 2^2 + 3^2 + … + n^2 = n(n+1)(2n+1)/6 = O(n^3)幾何級(jí)數(shù)：與末項(xiàng)同階
Ta(n) = a^0 + a^1 + a^2 + a^3 + … + a^n = (a^(n+1) -1)/(a-1) = O(a^n)收斂級(jí)數(shù)
和趨向一個(gè)常數(shù)：O(1)調(diào)和級(jí)數(shù)（log : 通常以 2 為底數(shù)）
h(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n = O(logn)
log1 + log2 + log3 + ... + logn = log(n!) = O(nlogn)-
Concrete Mathematics（建議閱讀書目）
筆記學(xué)習(xí)于
數(shù)據(jù)結(jié)構(gòu)(自主模式)-清華大學(xué)-鄧俊輝
筆記中代碼均出自該學(xué)習(xí)視頻
MOOC課程地址：
http://www.xuetangx.com/courses/course-v1:TsinghuaX+30240184+sp/about
