function - 如何计算此递归函数的最坏情况（理论）运行时间？

Question

我正在分析这段代码以查看如何计算最坏情况下的理论运行时间。我正在使用主定理。有人可以给我一个关于如何到达运行时间的分步解决方案吗？

def sort(list, i, j):
    if list[i] > list[j]:
        list[j], list[i] = list[i], list[j]
    if i + 1 >= j:
        return
    k = (j - i + 1)/3
    sort(list, i, j - k)
    sort(list, i + k, j)
    sort(list, i, j - k)

Answer 1

所以大师的定理是T(n) = a*T(n/b) + f(n)哪里a是子问题的数量，n/b是子问题的大小，f(n)是你每次调用必须完成的计算量。

a:有三个子问题，或三个递归调用，

n/b:每个子问题最多2/3输入原始数量。您可以为每一个证明它，但举个例子：sort(list, i, j-k)有一个问题大小来自(j-k) - i，即j-(j-i+1)/3 - i = (2j - 2i - 1)/3

f(n):是O(1)，或以常数时间为界，因为你只是在做两个常数时间开关。

这应该是关于O(n^(log(3) base (2/3)))数学符号的抱歉，我不确定如何在堆栈溢出时使用它。