时间戳

首页 > 解决方案 > 递归雪花函数的复杂度是多少？

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

问题描述

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

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

标签： recursioncomplexity-theoryfractalssnowflake-cloud-data-platform

解决方案

尽管该函数可能看起来很复杂，但值得注意的是，它的执行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)。

推荐阅读