Блог

 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);
}
  

Я прекрасно разобрался в сложностях сортировки слиянием, bubbleSort, но я так запутался в этом. В чем сложность этого алгоритма. Кто-нибудь может объяснить?

Это что-то вроде Марионетки. Это алгоритм, созданный для того, чтобы показать, что любителям действительно не следует внедрять свои собственные алгоритмы, не проанализировав их предварительно должным образом. Его время выполнения составляет приблизительно O (n ^ 3).

Выполнить вычисление не так уж сложно.

• Каждый раз, когда этот алгоритм выполняет 3 вызова самого себя, разделяя на 3 (равные) части часть входных данных текущего шага. Примечание: первый вызов и третий одинаковы.
• Локальная сложность — это просто O (1) (что означает константу), поскольку он будет выполнять только обмен, if и вычисление k