время выполнения модифицированного Stooge сортировки Алгоритм

Question

Я понимаю, что алгоритм Stooge сортировки работает следующим образом:

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 

Я также понимаю, что время выполнения марионетки рода О (п^(срубы 3/Журнал 1.5)).

Из любопытства, какова была бы продолжительность в нотации Big O, если бы мы полностью вытащили Шаг 1 и условие if на шаге 2 (при условии, что размер массива всегда будет делиться на три)?

Answer 1

На шаге 2 вам все еще нужно какое-то условие для не вызов stooge сортировать рекурсивно. В противном случае сортировка массива длиной 10 вызывает сортировку массива длиной 10 * 2/3, который вызывает сортировку массива длиной 10 * 2/3 * 2/3, ... который после нескольких шагов таким образом, вызовы сортируют массив длиной 0, который в свою очередь вызывает сортировку массива длины 0 снова и так далее бесконечно.

На шаге 1 вам все равно необходимо выполнить некоторую фактическую работу. В противном случае эту функцию можно назвать сортировкой, перетасовкой и т. Д., Но на самом деле бесполезно, поскольку нет шага, который меняет любые значения.

Итак, чтобы ответить на ваш вопрос, время выполнения будет бесконечным. Но каждое из двух изменений, которые вы предлагаете, нарушает алгоритм.