algorithm - 改进的 Stooge 排序算法的运行时

Question

我知道 Stooge Sort 算法的工作原理如下:

Step 1: If the value at the end is smaller than the value at the start, swap them.
Step 2: If there are 3 or more elements in the list, then:

       Stooge sort the initial 2/3 of the list
       Stooge sort the final 2/3 of the list
       Stooge sort the initial 2/3 of the list again

       else: exit the procedure

我还了解到 Stooge 排序的运行时间是 O(n^(log 3/log 1.5))。

出于好奇，如果我们完全去掉第 1 步和第 2 步中的 if 条件(假设数组大小总是能被 3 整除)，大 O 表示法的运行时间是多少？

Answer 1

在第 2 步，您仍然需要一些条件来不递归调用走狗排序。否则，对长度为 10 的数组进行排序会调用对长度为 10 * 2/3 的数组进行排序，这会调用对长度为 10 * 2/3 * 2/3 的数组进行排序，... 这样经过几步之后，调用对长度为 0 的数组进行排序，这又会再次调用对长度为 0 的数组进行排序，依此类推。

在第 1 步中，您仍然需要做一些实际工作。否则，该函数可能被称为排序、洗牌或其他任何名称，但实际上是无用的，因为没有交换任何值的步骤。

因此，要直接回答您的问题，运行时间将是无限的。但是您提出的两个更改中的每一个都破坏了算法。