对于某个比较简单的算法,我们有时候确实能够精确地分析出算法的复杂度。
比如算法复杂度为5n^2+10n+6,但是事实上并不需要这样,因为当n足够大时,可以忽略掉低阶项和最高次项的系数,因此就引出了“渐近复杂度”,并且用“渐近记号”来表示“渐近复杂度”。
渐近记号包括:
符号 | 含义 |
O | 渐进小于或等于 |
Ω | 渐进大于或等于 |
Θ | 渐进等于 |
举例:
如果a=x+x,b=x+5,则称a与b是相同等级的,且a渐进等于b;
如果a=x+x,b=x+5,则称a与b不是相同等级的,且a渐进小于或等于b,b渐进大于或等于a。
其中判断a和b是不是两个相同等级的,是依靠比较两个式子中自变量最高的次数,a=x+x 中自变量最高次数为2,b=x+5 中自变量最高次数为3。
如果两个自变量的最高次数相同,则说明它们是相同等级的,即他们俩渐进相等,
如果其中一个的次数比另一个高,则称次数低的一个式子渐进小于或等于次数高的式子,次数高的一个式子渐进大于或等于次数低的式子。
注意不要关注他们的系数谁大谁小,现在用符号表示语言:
a=x+x,b=x+5; ====> a=Θ(b);
a=x+x,b=x+5; ====> a=O(b) 或者 b=Ω(a);
其实,这个只要明白比较的是什么就能理解三个符号的含义及用法了。
简记为:O表示上界,Ω表示下界,Θ表示平行。
性能测量工具
Python自带了几个性能分析的模块:profile、cProfile和hotshot,使用方法基本都差不多,无非模块是纯Python还是用C写的。
cProfile的命令行用法
python -m cProfile XXX.py
输出到指定的文件:
python -m cProfile -o log.txt XXX.py
输出就被定向到了log.txt文件。
log.txt文件可以用VPT(http://visualpytune.googlecode.com)这样的图形工具打开。当log比较多的时候,可以很方便的进行过滤和时间的排序。
2145 function calls (2058 primitive calls) in 0.301 seconds Ordered by: standard name ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 _strptime.py:103(__calc_am_pm)
1 0.000 0.000 0.000 0.000 _strptime.py:115(__calc_date_time)
1 0.022 0.022 0.024 0.024 _strptime.py:12(<module>)
1 0.000 0.000 0.000 0.000 _strptime.py:160(__calc_timezone)
1 0.000 0.000 0.000 0.000 _strptime.py:176(TimeRE)
1 0.000 0.000 0.002 0.002 _strptime.py:179(__init__)
4 0.000 0.000 0.000 0.000 _strptime.py:212(<genexpr>)
6 0.000 0.000 0.000 0.000 _strptime.py:221(__seqToRE)
49 0.000 0.000 0.000 0.000 _strptime.py:236(<genexpr>)
4 0.000 0.000 0.001 0.000 _strptime.py:240(pattern)
1 0.000 0.000 0.001 0.001 _strptime.py:263(compile)
输出如上图,主要有:
ncalls:函数被call的次数
tottime:函数总的耗时,但是不包括其下的子函数的耗时
percall:tottime平均到每次调用的耗时
cumtime:函数总的耗时,包括了其子函数的耗时(递归函数也不例外)
percall:cumtime平均到每次调用的耗时
filename:lineno(function) :每个函数各自的信息
cProfile在Python代码中使用
import cProfile
cProfile.run('myfunction(arg1,arg2)', 'myfunction_prof')
使用以上的代码来引入cProfile, 并且使用其作为入口来调用待测函数。结果会放在myfunction_prof文件中。
这里再介绍一下结果文件在python下的阅读方法:
import pstats
p = pstats.Stats('myfunction_prof')
p.print_stats() # 可以设置排序方式,例如以花费时间多少排序
p.sort_stats('time').print_stats()
命令行中使用方法:
python -m pstats myfunction_prof
以上的内容,很容易在python的reference中找到,请参考: