时间戳

首页 > 解决方案 > 编写具有指定复杂度的递归算法

recursion - 编写具有指定复杂度的递归算法

问题描述

我正在学习算法分析课程，一个练习让我陷入困境，因为它要求的复杂性太具体了，这就是问题所在：

编写一个递归算法，给定一个整数 n 作为输入，打印 Θ(n^log4 11(log n)) 星号。为了证明复杂性，您可以使用主定理。

标签： recursiontime-complexity

解决方案

回忆一下主定理的第二种情况。如你所知，

T(n) = aT(n/b)+f(n)

如果f=Theta(n^log_{b}{a})那么 `T(n) = Theta(n^log_{b}{a}*logn)

因此，您需要对输入大小的 0.25 进行 11 次递归调用，并且在每次调用中执行n^log{4}{11}“工作”

因此，一个直接的方法将是：

define f (n):
m = floor(log_{4}{11})
print ('*' * pow(n,m))
for i in (0,11):
   f(floor(n/4))

推荐阅读