编写指定复杂度的递归算法

Question

我在上一门算法分析课程，有一个练习让我卡住了，因为它要求的复杂性和内容太具体了，这就是问题所在：

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

Answer 1

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

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))

Write recursive algorithm with especified complexity