發現樓層和天花板的遞歸對數算法的複雜性

我有這個醜陋的算法（是的，這是一門計算機科學課程，所以故意醜陋）。我們必須使用不同的方法來找到它的複雜性。其中一種方法是向後替換。僅僅通過查看算法，似乎很明顯它的複雜度將在（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不是真的。我不熟悉這種方法。 –

發現樓層和天花板的遞歸對數算法的複雜性

回答

相關問題