このソートアルゴリズムの複雑さは何ですか？

Question

template<class T> void sSort(T *A, int first, int last) 
{ 
    if(A[first]>A[last]) 
     swap(A[first],A[last]); 

    if(first+1>=last) 
    return; 
    double k = floor((last-first+1)/3); 


    sSort(A,first,last-k); 
    sSort(A,first+k,last); 
    sSort(A,first,last-k); 
} 

私はmergeSort、bubbleSortの複雑さを完全に理解しましたが、私はこのように混乱しています。このアルゴリズムの複雑さは？誰でも説明できますか？

Answer 1

を行うので

ローカル複雑さはわずかO（1）（定数を意味する）です。これは、アマチュアが最初に適切に解析することなく、独自のアルゴリズムを実装してはならないことを示すために構築されたアルゴリズムです。実行時間は約O（n^3）です。

Answer 2

これほど計算が難しくありません。

• このアルゴリズムは、現在のステップの入力の部分を3（等しい）部分に分割する呼び出しを毎回実行します。 注：最初の呼び出しと3番目の呼び出しは同じです。それはこれがStooge sortあるだけスワップ、AN場合及びkの計算