床と天井を持つ再帰的なログアルゴリズムの複雑さを見つける

Question

私はこの醜いアルゴリズムを持っています（はい、それはコンピュータサイエンスコースなので、目的には醜いです）。その複雑さはさまざまな方法で見つけなければなりません。メソッドの1つは後方への置換です。アルゴリズムを見るだけで、その再帰呼び出しごとにインスタンスサイズが3で割られるので、複雑さはlog（n - m）の範囲のどこかにあることは明らかです。

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（）に対処しようとしています。どのように対処するのですか？

私の本能は、彼らは脇に磨かれていることはできないと言いますが、それは私がやるべきことかもしれません。

また、アレイが既にソートされている場合、アルゴリズムが先に終了しないという事実を考慮すると、最悪の場合と最良の場合が同じだと思いますが、それも間違っている可能性があります。

Answer 1

申し訳ありませんが、複雑さはlog(x)から遠く離れています。

最悪の場合を想定します。m=1あなたのやっていることは、要素の2/3が3回繰り返されることです。私は私の推定は非常に遠くだったことを私が実現終了し、他の技術を介して行ったときに、マスターtheorm ==>T(n) = O(n^2.7~)