數(shù)據(jù)結(jié)構(gòu)主要研究組織大量數(shù)據(jù)的方法，算法分析則是對(duì)算法運(yùn)行時(shí)間的評(píng)估。
用下列四個(gè)定義表示函數(shù)增長(zhǎng)率的大?。?/p>
- 如果存在正常數(shù) c 和 n0 使得當(dāng) N>=n0 時(shí) T(N)<=cf(N), 則記為 T(N) = O(f(N)).
- 如果存在正常數(shù) c 和 n0 使得當(dāng) N>=n0 時(shí) T(N)>=cg(N), 則記為 T(N) = Ω(g(N)).
- T(N) = θ(h(N)) 當(dāng)且僅當(dāng) T(N) = O(h(N)) 且 T(N) = Ω(h(N)).
- 如果 T(N) = O(p(N)) 且 T(N) ≠ θ(p(N)), 則 T(N) = o(p(N)).
例如，T(N) = 1000N, f(N) = N^2
用大 O 記法表述為：1000N = O(N^2)
即：
- T(N) 增長(zhǎng)率小于等于 f(N).
- T(N) 增長(zhǎng)率大于等于 g(N).
- T(N) 增長(zhǎng)率等于 h(N).
- T(N) 增長(zhǎng)率小于 p(N).
幾個(gè)法則：
若 T1(N) = O(f(n)), T2(N) = O(g(n)), 則：
- T1(N) + T2(N) = max(O(f(N)), O(g(N)))
- T1(N) × T2(N) = O(f(N) × g(N)).
幾個(gè)典型的函數(shù)增長(zhǎng)率：
| 函數(shù) | 名稱 |
|---|---|
| c | 常數(shù) |
| logN | 對(duì)數(shù)級(jí) |
| (logN)^2 | 對(duì)數(shù)平方 |
| N | 線性級(jí) |
| NlogN | |
| N^2 | 平方級(jí) |
| N^3 | 立方級(jí) |
| 2^N | 指數(shù)級(jí) |
PS: N 的增長(zhǎng)率要快于 logN 的任意次冪。
運(yùn)行時(shí)間計(jì)算
計(jì)算 3次冪之和 的示例代碼：
int Sum(int N)
{
int i, PartialSum;
/* 1 */ PartialSum = 0;
/* 2 */ for (int i=1; i<=N; i++)
/* 3 */ PartialSum += i * i * i;
/* 4 */ return PartialSum;
}
運(yùn)行時(shí)間分析：
- 聲明不計(jì)時(shí)間；
- 第 1 行和第 4 行各占一個(gè)時(shí)間單元；
- 第 3 行每執(zhí)行一次占用 4 個(gè)時(shí)間單元（兩次乘法，一次加法，一次賦值），而執(zhí)行 N 次共占用 4N 個(gè)時(shí)間單元；
- 第 2 行在初始化 i, 測(cè)試 i<= N 和對(duì) i 的自增運(yùn)算中隱含著開銷（初始化1個(gè)時(shí)間單元，所有的測(cè)試 N+1 個(gè)時(shí)間單元，以及所有的自增運(yùn)算 N 個(gè)時(shí)間單元，共2N+2）。
我們忽略調(diào)用函數(shù)和返回值的開銷，得到總量是6N+4，因此我們說(shuō)該函數(shù)是 O(N).
計(jì)算運(yùn)行時(shí)間的一般法則
for 循環(huán)
一次 for 循環(huán)的運(yùn)行時(shí)間至多是該 for 循環(huán)內(nèi)語(yǔ)句（包括測(cè)試語(yǔ)句）的運(yùn)行時(shí)間乘以迭代次數(shù)。嵌套的 for 循環(huán)
從里向外分析。一組嵌套內(nèi)部的一條語(yǔ)句總的運(yùn)行時(shí)間為該語(yǔ)句的運(yùn)行時(shí)間乘以該組所有的 for 循環(huán)的大小的乘積。例如：
for (i=0; i<N; i++)
for (j=0; j<N; j++)
k++;
該程序片段為 O(N^2).
- 順序語(yǔ)句
將各個(gè)語(yǔ)句的運(yùn)行時(shí)間求和即可（即，其中的最大值）。例如，下述程序片段先用去 O(N), 再花費(fèi) O(N^2), 總開銷也是 O(N^2).
for (i=0; i<N; i++)
a[i] = 0;
for (i=0; i<N; i++)
for (j=0; j<N; j++)
a[i] += a[j] + i + j;
- if/else 語(yǔ)句
對(duì)程序片段
if (condition)
S1
else
S2
一個(gè) if/else 語(yǔ)句的運(yùn)行時(shí)間不超過判斷再加上 S1 和 S2 中運(yùn)行時(shí)間長(zhǎng)者的總運(yùn)行時(shí)間。
