|
对于某个比较简单的算法，我们有时候确实能够精确地分析出算法的复杂度。
比如算法复杂度为5n^2+10n+6，但是事实上并不需要这样，因为当n足够大时，可以忽略掉低阶项和最高次项的系数，因此就引出了“渐近复杂度”，并且用“渐近记号”来表示“渐近复杂度”。
渐近记号包括：
| 符号 |
含义 |
| O |
渐进小于或等于 |
| Ω |
渐进大于或等于 |
| Θ |
渐进等于 |
举例：
如果a=x2+x,b=x2+5，则称a与b是相同等级的，且a渐进等于b；
如果a=x2+x,b=x3+5，则称a与b不是相同等级的，且a渐进小于或等于b，b渐进大于或等于a。
其中判断a和b是不是两个相同等级的，是依靠比较两个式子中自变量最高的次数，a=x2+x 中自变量最高次数为2，b=x3+5 中自变量最高次数为3。
如果两个自变量的最高次数相同，则说明它们是相同等级的，即他们俩渐进相等，
如果其中一个的次数比另一个高，则称次数低的一个式子渐进小于或等于次数高的式子，次数高的一个式子渐进大于或等于次数低的式子。
注意不要关注他们的系数谁大谁小，现在用符号表示语言：
a=x2+x,b=x2+5； ====> a=Θ(b);
a=x2+x,b=x3+5； ====> a=O(b) 或者 b=Ω（a）；
其实，这个只要明白比较的是什么就能理解三个符号的含义及用法了。
简记为：O表示上界，Ω表示下界，Θ表示平行。
性能测量工具
Python自带了几个性能分析的模块：profile、cProfile和hotshot，使用方法基本都差不多，无非模块是纯Python还是用C写的。
cProfile的命令行用法
1 | python -m cProfile XXX.py
|
输出到指定的文件：
1 | python -m cProfile -o log.txt XXX.py
|
输出就被定向到了log.txt文件。
log.txt文件可以用VPT（http://visualpytune.）这样的图形工具打开。当log比较多的时候，可以很方便的进行过滤和时间的排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | 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代码中使用
1 2 | import cProfile
cProfile.run('myfunction(arg1,arg2)', 'myfunction_prof')
|
使用以上的代码来引入cProfile, 并且使用其作为入口来调用待测函数。结果会放在myfunction_prof文件中。
这里再介绍一下结果文件在python下的阅读方法：
1 2 3 4 5 6 | import pstats
p = pstats.Stats('myfunction_prof')
p.print_stats()
# 可以设置排序方式，例如以花费时间多少排序
p.sort_stats('time').print_stats()
|
命令行中使用方法：
1 | python -m pstats myfunction_prof
|
以上的内容，很容易在python的reference中找到，请参考：
http://docs./2/library/profile.html
|
