发现楼层和天花板的递归对数算法的复杂性

我有这个丑陋的算法（是的，这是一门计算机科学课程，所以故意丑陋）。我们必须使用不同的方法来找到它的复杂性。其中一种方法是向后替换。仅仅通过查看算法，似乎很明显它的复杂度将在（log（n-m））范围内，因为实例大小在每次递归调用时除以3。发现楼层和天花板的递归对数算法的复杂性

Function WeirdSort(Array[m..n]) 
    if (m < n) then 
     if (A[m] > A[n]) then 
      temp = A[m] 
      A[m] = A[n] 
      A[n] = temp 
     end if 
     if (m + 1 < n) then 
      index = floor((n - m + 1)/3) 
      WeirdSort(A[m..n - index]) 
      WeirdSort(A[m + index..n]) 
      WeirdSort(A[m..n - index]) 
     end if 
    end if 
end Function

但我想了解如何通过反向替代方法来达到这个答案。更具体地说，我坚持试图处理开始显示数组大小的众多floor（）和ceiling（），以及我应该如何处理它们。

我的直觉告诉我，他们不能被抛在一边，但也许这是我应该做的？此外，考虑到如果数组已经排序，算法不会提前结束，我认为最差和最好的情况是相同的，但这也可能是错误的。

来源

2017-02-15 Kaito Kid

很抱歉告诉你，但其复杂性远离log(x)。

假设最坏的情况，其中m=1你做什么是递归2/3元素的3倍。

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

使用主表示定理==>T(n) = O(n^2.7~)

来源

2017-02-15 21:44:32

谢谢您的输入，当我通过其他技术我最终意识到，我的估计是很离谱去了。另一方面，你并没有真正回答这个问题，这个问题是关于使用反向替代方法达到这个答案的过程。你知道这件事吗？ –

@KaitoKid不是真的。我不熟悉这种方法。 –

发现楼层和天花板的递归对数算法的复杂性

回答

相关问题