这种排序算法的复杂性是什么？

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的复杂性，但我很困惑这一个。这个算法的复杂性是什么。谁能解释一下？这种排序算法的复杂性是什么？

来源

2011-11-10 LuckySlevin

你可以只尝试不同尺寸的几个阵列，运行它，看看时间比较数组的大小... – Mehrdad

的计算这是Stooge sort。这是一个算法，用来表明业余爱好者如果没有正确分析它们，就不应该实现自己的算法。它的运行时间大约是O（n^3）。

来源

2011-11-11 00:06:21 bdares

谢谢你，这个链接帮助我获得更多的文档。 – LuckySlevin

谁发明了stoogesort？ – AShelly

这不是太难做了计算。

每次这个算法做3次调用将其自身分裂成3（相等）部分当前步骤的输入部分。注意：第一个电话和第三个电话是一样的。
的局部复杂性仅仅是一个O（1）（这意味着恒定），因为它会做只是交换，一个if并且k

来源

2011-11-10 23:50:57

我对这种事情生疏，但我认为这是一个有点更多地参与为三递归调用在重叠的值范围上操作。 – Lars

我实际上坚持3个电话，我不能计算他们，我会有点疯狂:) – LuckySlevin

实际上算法的作品，但如此缓慢，你可以尝试运行它:)。算法中不存在任何错误。 – LuckySlevin

这种排序算法的复杂性是什么？

回答

相关问题