算法时间频度介绍和特点

算法的时间复杂度

时间频度

何为时间频度

时间频度:一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为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+7n3n^2 + 2n ,执行曲线重合, 说明 这种情况下, 5和3可以忽略。 而n^3+5n6n^3+4n ,执行曲线分离,说明多少次方式关键

本作品采用《CC 协议》,转载必须注明作者和本文链接
秋叶夏风
victorfengming
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!