递归复杂度
- 接前面
- 常见初等函数的变化曲线
- T ( n ) = a ∗ T ( n / b ) + O ( n d ) T(n) = a*T(n/b)+O(n^d) T(n)=a∗T(n/b)+O(nd)
- a a a
- b b b
- d d d
- 推导
- T ( n ) = 4 ∗ T ( n / 1.3 ) + O ( n 0 ) T(n) = 4*T(n/1.3)+O(n^0) T(n)=4∗T(n/1.3)+O(n0)
接前面
反恐搜索——打印间隔两枚选择的硬币里一百个数据要一个小时还没有运行完成。它的复杂度是指数级的吗？
常见初等函数的变化曲线
 书中插图 |
|---|
T ( n ) = a ∗ T ( n / b ) + O ( n d ) T(n) = a*T(n/b)+O(n^d) T(n)=a∗T(n/b)+O(nd)
T ( n ) T(n) T(n) 代表递归方法处理规模为n的数据量的时间复杂度， a ∗ T ( n / b ) a*T(n/b) a∗T(n/b) 代表调用子递归方法的总体时间复杂度， O ( n d ) O(n^d) O(nd) 代表递归方法其他代码的时间复杂度。
a a a
a a a: 每次递归调用子问题的数量。即在一个递归方法，需要调用几次子递归方法。
b b b
b b b: 子问题的规模缩小的比例。例如二分法递归搜索时，每次需要查找的数据都缩小了一半，那么 b = 2 b=2 b=2
d d d
d d d: 每次递归调用之外的代码时间复杂度的参数。例如二分法递归搜索时，每次递归时除了调用递归的方法，没有什么for循环代码，时间复杂度是 O ( 1 ) O(1) O(1)，即 n d = 1 n^d=1 nd=1，因此 $d=0%
推导
1、 d < log b a d<\log_{b}a d<logba
递归时间复杂度为： O ( n log b a ) O(n^{\log_{b}{a}}) O(nlogba)
2、 d = log b a d=\log_{b}a d=logba
递归时间复杂度为： O ( n d ∗ log n ) O(n^d *{\log_{}{n}}) O(nd∗logn)
2、 d > log b a d>\log_{b}a d>logba
递归时间复杂度为： O ( n d ) O(n^d) O(nd)
T ( n ) = 4 ∗ T ( n / 1.3 ) + O ( n 0 ) T(n) = 4*T(n/1.3)+O(n^0) T(n)=4∗T(n/1.3)+O(n0)
a
=
4
a=4
a=4有四个递归调用，
b
=
1.3
b=1.3
b=1.3原来一百的数量，最坏的跳过一个就是
100
99
\frac{100}{99}
99100，到最后最好是五个的时候跳过四个
5
1
\frac{5}{1}
15，取两个的中值1.3吧。
d
=
0
d=0
d=0 max是调用的Python,几乎常数级别。
log
1.3
4
=
5.283853591622281
\log_{1.3}4=5.283853591622281
log1.34=5.283853591622281
10
0
5.283853591622281
=
36957891253.5873
100^{5.283853591622281}=36957891253.5873
1005.283853591622281=36957891253.5873
与20个数字对比
20个算出的复杂度是7489486.036335511，100个数字的复杂度是它的4934.636512343405倍。测试20个用时0.42999982833862305秒。
s=time.time()
row = [552, 440, 606, 818, 756, 577, 266, 312, 174, 692, 492, 635, 92, 644, 571, 51, 732, 357, 110, 545]
_, table = coins2(row,{})
print(time.time()-s)
0.42999982833862305
{0: 0, 1: 545, 2: 655, 3: 655, 4: 1277, 5: 1328, 6: 1328, 7: 1921, 8: 2013, 9: 2055, 10: 2455, 11: 3105, 12: 3105, 13: 3105, 14: 3371, 15: 3948, 16: 4438, 17: 4679, 18: 4795, 19: 4994, 20: 5430}
这样看一个小时应该会有答案。是不是问题的缩小规模没有那么大？
1.1
从5次方变成了14次方。
>>> import math
>>> math.log(4,1.1)
14.545081794683426
>>>
那就是20个数字用时的13647875839.232113倍，要186年完成计算。
>>> 0.42999982833862305*13647875839.232113/(3600*24*365)
186.0915863792697
指数级的复杂度
从开头的图也可以看出3次方的时候就直接竖上去了。20以内的数据量还可以承受的。
标签：20,log,递归,1.3,复杂度,nd,算法 From： https://blog.csdn.net/denghai_csdn/article/details/143566153