时间频度

何为时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。[举例说明]

举例说明-基本案例

比如计算1-100所有数字之和, 我们设计两种算法：
image-20210222135219083
T(n)=n+1;
image-20210222135250428
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 |

image-20210222135534763

结论:

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 |

image-20210222135717981

结论:

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 |

image-20210222140019981

结论:

随着n值变大，5n^2+7n 和3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5和3可以忽略。
而n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键
使用Obsidian