Какова сложность рекурсивной функции снежинки?

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 имеет 3 идентичных вызова на fractal, так же как и O(3^n).