Stooge Sort递归树的大O分析

Question

我试图找到Big O进行stooge排序.来自维基百科

algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ? L[j]
     if j - i > 1 then
         t = (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

我在性能分析方面表现不佳......我绘制了递归树

我相信...:

• 高度: log(n)
• 在0级工作:n //我是从0级还是1级开始？
• 工作在1级:2n
• 工作在2级:4n
• 在3级工作:8n
• 在级别log(n)上工作:(2^log(n))n = O(n^2)？2^log2(n) = n,但它2^log3(n)实际上给了什么？

那么O(n^2 * log(n)) = O(n^2)呢？它远离维基百科O(n^(log3/log1.5))......

Answer 1

级别k的问题大小为(2/3)^k n.最低级别的大小为1,因此设置(2/3)^k n = 1,深度为k = log _1.5 n(将两边除以(2/3)^k,取记录基数1.5).

级别k的调用次数为3 ^k.在级别k = log _1.5 n,这是3 ^{log _1.5 n} =((1.5)^{log _1.5 3})^{log _1.5 n} =((1.5)^{log _1.5 n})^{log _1.5 3} = n ^{log _1.5 3} = n ^{log 3/log 1.5}.

由于每个级别的工作在几何上增加,叶子上的工作占主导地位.

Answer 2

您可以使用主定理来查找此答案.我们可以从算法中看到递归关系是:

T(n)= 3*T(2/3 n)+ 1

应用该定理:

f(n)= 1 = O(n ^c),其中c = 0.a = 3,b = 3/2 => log3/2(3)= ~2.70

由于c <log3/2(3),我们在定理的情况1中,因此:

T(n)= O(n ^log3/2(3))= O(n ^2.70)