目标
算法分析重要性
学会使用算法分析工具大O记号来描述时间复杂度
理解常用数据结构的时间复杂度
理解数据如何影响算法分析
如何对程序做基准测试 benchmark
什么是算法分析
考虑解决同一个问题采用不同的代码解决所需要的计算机资源,或者考虑其执行所需要花费的时间。
很多情况下,我们考虑时间。
在程序中,可以
import time
start = time.time()
CODE BLOCK
end = time.time()
runtime= end - start
不同的计算机,语言等都会带来时间的差异。因此,这个time并不能真正度量。
我们通过一种大O记号来避开这些影响。
大O记号
我们以程序执行的步数为基准,来计算时间。
乱序字符串
一个字符串是另一个字符串的重新排列。如
heart 和raeth。asdfg和gfdas.
如何判断两个字符串是否为乱序字符串?
- 排序法:两字符串分别排序后是否相等,其时间复杂度需要考虑排序算法的时间复杂度。
- 穷举法
- 字符计数
网友评论