For faster navigation, this Iframe is preloading the Wikiwand page for 算法分析.

# 算法分析

## 时间资源消耗

• 单一消耗：每一步操作的消耗定义为一个常量，与参与运算的数据的大小无关。
• 对数消耗：每一步操作的消耗，均与参与运算的数据的长度（位数）成正比。

### 经验分析的缺陷

（以纳秒计）

（以纳秒计）
15 7 100,000
65 32 150,000
250 125 200,000
1,000 500 250,000

（以纳秒计）

（以纳秒计）
15 7 100,000
65 32 150,000
250 125 200,000
1,000 500 250,000
... ... ...
1,000,000 500,000 500,000
4,000,000 2,000,000 550,000
16,000,000 8,000,000 600,000
... ... ...
63,072 × 1012 31,536 × 1012纳秒，

1,375,000 纳秒，

### 运行时间复杂度的分析

1    从输入值中获取一个正数
2    if n > 10
3        print "耗时可能较长，请稍候……"
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "完成！"


${\displaystyle T_{1}+T_{2}+T_{3}+T_{7))$

${\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6))$

${\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2))(n^{2}+n)\right]}$

${\displaystyle 2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5))$
${\displaystyle =T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5))$

${\displaystyle T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5))$
${\displaystyle =\left[{\frac {1}{2))(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5))$
${\displaystyle =T_{5}\left[{\frac {1}{2))(n^{2}+n)\right]+nT_{5))$
${\displaystyle =\left[{\frac {1}{2))(n^{2}+3n)\right]T_{5))$

${\displaystyle f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2))(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2))(n^{2}+3n)\right]T_{5))$

${\displaystyle f(n)=\left[{\frac {1}{2))(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2))(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7))$

${\displaystyle \left[{\frac {1}{2))(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2))(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7))$

${\displaystyle \leq (n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ (n\geq 0)}$

${\displaystyle T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k}$

${\displaystyle =2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\,(n\geq 1)=12kn^{2))$

${\displaystyle \left[{\frac {1}{2))(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2))(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0))$，其中 ${\displaystyle c=12k,n_{0}=1}$

${\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\,(n\geq 1)=O(n^{2}).}$

## 其他运算资源的增长率分析

while (文件打开)
令 n = 文件大小
for n 每增长 100kb
为该文件分配多一倍的内存空间


## 注释

1. ^ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman. The design and analysis of computer algorithms. Addison-Wesley Pub. Co. 1974., section 1.3
2. ^ Juraj Hromkovič. Theoretical computer science: introduction to Automata, computability, complexity, algorithmics, randomization, communication, and cryptography. Springer. 2004: 177–178. ISBN 978-3-540-14015-3.
3. ^ Giorgio Ausiello. Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer. 1999: 3–8. ISBN 978-3-540-65431-5.
4. ^ Wegener, Ingo, Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag: 20, 2005, ISBN 978-3-540-21045-0
5. ^ Robert Endre Tarjan. Data structures and network algorithms. SIAM. 1983: 3–7. ISBN 978-0-89871-187-5.
6. ^ Examples of the price of abstraction?, cstheory.stackexchange.com
7. ^ 在算法分析的场合里，常用 ${\displaystyle \log }$${\displaystyle \lg }$ 作为 ${\displaystyle \log _{2))$ 的简称。
8. ^ 但这对量子计算机不成立。
9. ^ 可用数学归纳法证明 ${\displaystyle 1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2))}$
10. ^ 比起上面的方法，这个方法忽略了结束循环的判断语句所消耗的时间，但很明显可以证明这种忽略不影响最后结果。

### 来源

{{bottomLinkPreText}} {{bottomLinkText}}

Listen to this article