Как мне написать что-то хуже, чем O (n!)

Question

Я написал O (n!) Для моего развлечения, которое нельзя просто оптимизировать для ускорения без полной его замены. [И нет, я не просто рандомизировал предметы, пока они не были отсортированы].

Как я мог бы написать еще худшую сортировку Big-O, просто не добавляя посторонний мусор, который можно было бы извлечь, чтобы уменьшить сложность времени?

http://en.wikipedia.org/wiki/Big_O_notation имеет различные временные сложности, отсортированные в порядке возрастания.

Edit: я нашел код, вот мой O (n!) Детерминированный вид с забавным хаком для генерации списка всех комбинаций списка. У меня есть немного более длинная версия get_all_combination, которая возвращает итеративные комбинации, но, к сожалению, я не смог сделать это ни одним утверждением. [Надеюсь, я не вносил ошибок, исправляя опечатки и удаляя подчеркивания в приведенном ниже коде]

def mysort(somelist):
    for permutation in get_all_permutations(somelist):
        if is_sorted(permutation):
            return permutation

def is_sorted(somelist):
    # note: this could be merged into return... something like return len(foo) <= 1 or reduce(barf)
    if (len(somelist) <= 1): return True
    return 1 > reduce(lambda x,y: max(x,y),map(cmp, somelist[:-1], somelist[1:]))

def get_all_permutations(lst):
    return [[itm] + cbo for idx, itm in enumerate(lst) for cbo in get_all_permutations(lst[:idx] + lst[idx+1:])] or [lst]

Answer 1

Существует (проверенный!) Алгоритм наихудшей сортировки, называемый медленная сортировка , который использует парадигму «умножить и сдать» и работает в экспоненциальном времени.

Хотя ваш алгоритм медленнее, он не прогрессирует стабильно, а выполняет случайные прыжки. Кроме того, лучший вариант медленной сортировки по-прежнему экспоненциальный, а ваш - постоянный.

Answer 2

Крис и я упомянул Бозосорт и Богосорт в другом вопросе.

Answer 3

Всегда есть NeverSort, то есть O (∞):

def never_sort(array)
  while(true)
  end
  return quicksort(array)
end

PS: я действительно хочу увидеть вашу детерминированную O (n!) Сортировку; Я не могу думать ни о каких, которые являются O (n!), Но имеют конечную верхнюю границу в классических вычислениях (иначе детерминированные).

PPS: Если вы беспокоитесь о том, что компилятор удаляет этот пустой блок while, вы можете заставить его этого не делать, используя переменную как внутри, так и вне блока:

def never_sort(array)
  i=0
  while(true) { i += 1 }
  puts "done with loop after #{i} iterations!"
  return quicksort(array)
end

Answer 4

Вот самая медленная, конечная сортировка, которую вы можете получить:

Свяжите каждую операцию быстрой сортировки с функцией Busy Beaver.

К тому времени, когда вы получите> 4 операции, вам понадобится нотация вверх-стрелка

Answer 5

Вы всегда можете сделать случайную сортировку. Он работает путем случайной перестановки всех элементов, а затем проверяет, отсортированы ли они. Если нет, он случайным образом прибегает к ним. Я не знаю, как это вписалось бы в нотацию big-O, но это определенно будет медленно!

Answer 6

Как насчет цикла по всем массивам t из n целых чисел (n-кортежей целых чисел счетны, так что это выполнимо, хотя это, конечно, бесконечный цикл), и для каждого из них:

• если его элементы в точности совпадают с элементами входного массива (см. Алгоритм ниже!) И массив отсортирован (например, с линейным алгоритмом, но я уверен, что мы можем сделать хуже), тогда вернуть t;
• в противном случае продолжить цикл.

Чтобы проверить, что два массива a и b длины n содержат одинаковые элементы, как насчет следующего рекурсивного алгоритма: переберите все пары (i, j) индексов от 0 до n-1 и для каждой такой пары

• проверка, если a [i] == b [j]:
• если это так, вернуть TRUE, если и только если рекурсивный вызов в списках, полученных путем удаления a [i] из a и b [j] из b, возвращает TRUE;
• продолжить цикл по парам, и, если все пары выполнены, вернуть FALSE.

Время будет сильно зависеть от распределения целых чисел во входном массиве.

Если серьезно, есть ли смысл в таком вопросе?

Edit:

@ Jon, ваша случайная сортировка будет в среднем по O (n!) (Поскольку существует n! Перестановок, у вас есть вероятность 1 / n! Найти правильную). Это верно для массивов различных целых чисел, может немного отличаться, если некоторые элементы имеют несколько вхождений во входном массиве, и будет зависеть от распределения элементов входных массивов (в целых числах).

Answer 7

Я думаю, что если вы много копируете, вы можете получить «разумный» поиск методом грубой силы (N!), Который будет занимать N ^ 2 раза в каждом случае, давая N! * N ^ 2

Answer 8

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

Я не уверен, что это даст вам O (n!), Но все равно должно быть довольно медленным.