算法的时间复杂度
时间频度
何为时间频度
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]
举例说明-基本案例
比如计算1-100所有数字之和, 我们设计两种算法：
T(n)=n+1;
T(n)=1
举例说明-忽略常数项
| T(n)=2n+20 | T(n)=2*n | T(3n+10) | T(3n) | |
|---|---|---|---|---|
| 1 | 22 | 2 | 13 | 3 |
| 2 | 24 | 4 | 16 | 6 |
| 5 | 30 | 10 | 25 | 15 |
| 8 | 36 | 16 | 34 | 24 |
| 15 | 50 | 30 | 55 | 45 |
| 30 | 80 | 60 | 100 | 90 |
| 100 | 220 | 200 | 310 | 300 |
| 300 | 620 | 600 | 910 | 900 |
结论:
2n+20 和 2n 随着n 变大，执行曲线无限接近, 20可以忽略 3n+10 和 3n 随着n 变大，执行曲线无限接近, 10可以忽略
举例说明-忽略低次项
| T(n)=2n^2+3n+10 | T(2n^2) | T(n^2+5n+20) | T(n^2) | |
|---|---|---|---|---|
| 1 | 15 | 2 | 26 | 1 |
| 2 | 24 | 8 | 34 | 4 |
| 5 | 75 | 50 | 70 | 25 |
| 8 | 162 | 128 | 124 | 64 |
| 15 | 505 | 450 | 320 | 225 |
| 30 | 1900 | 1800 | 1070 | 900 |
| 100 | 20310 | 20000 | 10520 | 10000 |
结论:
2n^2+3n+10 和 2n^2 随着n 变大, 执行曲线无限接近, 可以忽略 3n+10
n^2+5n+20 和 n^2 随着n 变大,执行曲线无限接近, 可以忽略 5n+20
同阶无穷大
举例说明-忽略系数
| T(3n^2+2n) | T(5n^2+7n) | T(n^3+5n) | T(6n^3+4n) | |
|---|---|---|---|---|
| 1 | 5 | 12 | 6 | 10 |
| 2 | 16 | 34 | 18 | 56 |
| 5 | 85 | 160 | 150 | 770 |
| 8 | 208 | 376 | 552 | 3104 |
| 15 | 705 | 1230 | 3450 | 20310 |
| 30 | 2760 | 4710 | 27150 | 162120 |
| 100 | 30200 | 50700 | 1000500 | 6000400 |
结论:
随着n值变大，5n^2+7n 和3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5和3可以忽略。
而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键
使用Obsidian