이 정렬 알고리즘의 복잡성은 무엇입니까?

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

의 계산 이것은 Stooge sort 경우 그냥 스왑 할 것이기 때문이다. 이것은 아마추어가 제대로 분석하지 않고 자체 알고리즘을 구현해서는 안된다는 것을 보여주기 위해 구성된 알고리즘입니다. 실행 시간은 약 O (n^3)입니다.

Answer 2

계산하기가 너무 어렵지 않습니다.

• 이 알고리즘은 현재 단계의 입력 부분을 3 (동등한) 부분으로 나눠서 호출 할 때마다. 참고 : 첫 번째 호출과 세 번째 호출은 동일합니다.
• 로컬 복잡성은 단지 O (1) (상수 의미)와 K