algorithm - 大 O 分析与 Stooge 排序的递归树

Question

我正在努力寻找 Big O 来进行走狗排序。来自维基百科

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)^kn。最底层的size为1，所以设(2/3)^kn = 1，深度k = log_1.5 n(两边除以(2/3)^k，取以 1.5 为底的日志。

第k层的调用次数为3^k。在级别 k = log_1.5 n，这是 3^log_1.5n = ((1.5)^log_1.53)^{log_1.5 n} = ((1.5)^log_1.5n)^{log_1.5 3} = n^log_1.53 = n^{log 3/log 1.5}.

由于每一层的工作量呈几何级数增长，所以叶层的工作量占主导地位。