递归雪花函数的复杂度是多少？

Question

# The base case basically draws a segment.

import turtle
def fractal(order,length):
    if order==0:
        turtle.forward(length)
    else:
        l=length/3
        fractal(order-1,l)
        turtle.left(60)
        fractal(order-1,l)
        turtle.right(120)
        fractal(order-1,l)
        turtle.left(60)
        fractal(order-1,l)
def snowflake(order,length):
    fractal(order,length)
    turtle.right(120)
    fractal(order,length)
    turtle.right(120)
    fractal(order,length)
snowflake(3,300)
turtle.speed(0)
turtle.done()

这是一个跟踪分形雪花的递归函数。 复杂度取决于顺序。 但是，当我们对每个订单执行如此多的递归操作时，我无法弄清楚。

Answer 1

虽然函数看起来复杂，但值得注意的是fractal 的执行仅依赖于order。所以在复杂性方面，它可以减少到：

def fractal(order):
    if order == 0:
         # do O(1)
    else:
        fractal(order - 1)
        fractal(order - 1)
        fractal(order - 1)

即3 次递归调用 order - 1；时间复杂度递归就很简单了：

T(n) = 3 * T(n - 1) (+ O(1))
T(1) = O(1)

– 很容易得出 O(3^n)。

snowflake 对 fractal 有 3 次相同的调用，O(3^n).

也是如此