这个递归的时间复杂度是多少？

Question

def s_r(n):
    if(n==1):
       return 1
    temp = 1
    for i in range(int(n)):
        temp += i
    return temp * s_r(n/2) * s_r(n/2) * s_r(n/2) * s_r(n/2)

使用递归树有什么了不起哦还有我们如何将这个函数写成一个递归调用。

我只能做我得到 O(n^2) 的第一部分。这是我的考题之一，我想知道答案和指导。谢谢

Answer 1

正如@kcsquared 在评论中所说，我也相信这个函数是 O(n²)。通过存储递归调用的结果，或者只是做一些数学应用，这段代码可以重构为一个函数调用。您还可以通过使用 built-in sum

来简化范围总和

def s_r(n):
    if n == 1:
        return 1
    return (sum(range(int(n))) + 1) * s_r(n/2) ** 4

Answer 2

首先，注意程序不正确：n/2是python中的浮点除法（因为Python3），所以程序不会终止，除非n是的幂2（或最终四舍五入为 2 的幂）。适用于所有整数 n>=1 的程序的更正版本是：

def s_r(n):
    if(n==1):
       return 1
    temp = 1
    for i in range(n):
        temp += i
    return temp * s_r(n//2) * s_r(n//2) * s_r(n//2) * s_r(n//2)

如果T(n)是函数执行的算术运算次数，那么我们有递归关系：

T(1) = 0
T(n) = n + 4T(n//2)

T(n) 是 Theta(n^2)——对于 n 的 2 次幂和伸缩我们得到：n + 4(n/2) + 16(n/4) + .. . = 1n + 2n + 4n + 8n + ... + nn = (2n-1)n

我们可以重写程序以使用 Theta(log n) 算术运算。首先，temp 变量是 1 + 0+1+...+(n-1) = n(n-1)/2 + 1。其次，我们可以避免进行 4 次相同的递归调用。

def s_r(n):
    return (1 + n * (n-1) // 2) * s_r(n//2) ** 4 if n > 1 else 1

回到复杂性，我一直小心地说第一个函数做Theta(n^2) 算术运算，第二个函数做Theta(log n) 算术运算，而不是使用“时间复杂度”这个表达方式。函数的结果增长很快，所以在 O(1) 时间内假设算术运算运行是不切实际的。如果我们打印结果的长度和计算它所花费的时间（使用第二个，更快的代码版本）使用这个......

import math
import timeit

def s_r(n):
    return (1 + n * (n-1) // 2) * s_r(n//2) ** 4 if n > 1 else 1


for i in range(16):
    n = 2 ** i
    start = timeit.default_timer()
    r = s_r(n)
    end = timeit.default_timer()
    print('n=2**%d,' % i, 'digits=%d,' % (int(math.log(r))+1), 'time=%.3gsec' % (end - start))

...我们得到这个 table，其中您可以看到结果中的位数快速增长（例如 s_r(2**14) 有 1.01 亿位），并且测量的时间确实不会随 log(n) 增长，但是当 n 加倍时，时间会增加大约 10 倍，因此它会增长 n^3 或 n^4。

n=2**0, digits=1, time=6e-07sec
n=2**1, digits=1, time=1.5e-06sec
n=2**2, digits=5, time=9e-07sec
n=2**3, digits=23, time=1.1e-06sec
n=2**4, digits=94, time=2.1e-06sec
n=2**5, digits=382, time=2.6e-06sec
n=2**6, digits=1533, time=3.8e-06sec
n=2**7, digits=6140, time=3.99e-05sec
n=2**8, digits=24569, time=0.000105sec
n=2**9, digits=98286, time=0.000835sec
n=2**10, digits=393154, time=0.00668sec
n=2**11, digits=1572628, time=0.0592sec
n=2**12, digits=6290527, time=0.516sec
n=2**13, digits=25162123, time=4.69sec
n=2**14, digits=100648510, time=42.1sec
n=2**15, digits=402594059, time=377sec

注意，原函数时间复杂度O(n^2)和改进版代码O(log n)的时间复杂度并没有错，只是这些描述了程序的一个度量（算术运算）并且作为实际程序的估计根本没有用运行宁时间。

这个递归的时间复杂度是多少？

What is the time complexity of this recursion?

python

algorithm

time-complexity