Существует ли алгоритм сортировки, который сортирует по O (∞) перестановкам?

Question

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

Другими словами, есть ли процесс?где можно попытаться сравнить и переупорядочить фиксированный набор данных и еще никогда не достичь фактического отсортированного списка?

Это гораздо более теоретический / философский вопрос, чем практический, и если бы я был болеематематика, я бы, вероятно, смог доказать / опровергнуть такую ​​возможность.Кто-нибудь задавал этот вопрос раньше, и если да, что можно сказать по этому поводу?

Answer 1

[edit:] ни один детерминированный процесс с конечным количеством состояний не принимает "O (бесконечность)", поскольку самое медленное, что может быть, - это пройти через все возможные состояния. это включает в себя сортировку.

[ранее, более конкретный ответ:] нет. для списка размера n у вас есть только пространство состояний размера n! в котором можно сохранить прогресс (при условии, что все состояние сортировки хранится в порядке расположения элементов, и оно действительно «делает что-то» детерминистически).

таким образом, наихудшее возможное поведение будет циклически проходить через все доступные состояния перед завершением и займет время, пропорциональное n! (рискуя запутать вопросы, через состояние должен быть один путь - поскольку это «все состояние», процесс не может быть переведен из состояния X в Y, а затем из состояния X в Z, поскольку это требует дополнительное состояние или является недетерминированным)

Answer 2

Идея 1:

function sort( int[] arr ) {
    int[] sorted = quicksort( arr ); // compare and reorder data
    while(true); // where'd this come from???
    return sorted; // return answer
}

Идея 2

Как вы определяете O(infinity)? Формальное определение Big-O просто утверждает, что f(x)=O(g(x)) подразумевает, что M*g(x) является верхней границей f(x) при достаточно большом x и некоторой константе M.

Обычно, когда вы говорите о «бесконечности», вы говорите о некоем неограниченном пределе. Поэтому в данном случае единственное разумное определение гласит, что O(infinity) - это O(function that's larger than every function). Очевидно, что функция, которая больше, чем каждая функция, является верхней границей. Таким образом, технически все "O(infinity)"

Идея 3

Предполагая, что вы имеете в виду тэта-нотацию (жесткую границу) ...

Если вы налагаете дополнительное ограничение на то, что алгоритм является умным (возвращается, когда он находит отсортированную перестановку), и каждая перестановка списка должна посещаться за конечное время, тогда ответ «нет». Есть только N! перестановок списка. Верхняя граница для такого алгоритма сортировки является конечной по конечным числам, которая является конечной.

Answer 3

Ваш вопрос не имеет ничего общего с сортировкой.Алгоритм, который гарантированно никогда не завершится, будет довольно скучным.Действительно, даже алгоритм, который мог бы или не мог бы завершиться, был бы довольно скучным.Гораздо более интересным был бы алгоритм, который в конечном итоге гарантированно завершился бы, но чье время вычисления наихудшего случая относительно размера входных данных не было бы выразимо как O (F (N)) для любой функции F, которая могла бы самарассчитываться в ограниченное время.Я догадывался, что такой алгоритм мог бы быть разработан, но я не уверен, как.

Answer 4

  Input:      A[1..n] : n unique integers in arbitrary order
  Output:     A'[1..n] : reordering of the elements of A
              such that A'[i] R(A') A'[j] if i < j.
  Comparator: a R(A') b iff A'[i] = a, A'[j] = b and i > j

В более общем плане, сделать компаратор чем-то, что либо (а) невозможно согласовать с выходной спецификацией, так что решение не может существовать, либо (б) невычислимо (например, отсортировать эти пары (входной, механизм Тьюринга) по порядку: количество шагов, необходимых для остановки машины на входе).

В более общем смысле, если у вас есть процедура, которая не может быть остановлена ​​на допустимом вводе, процедура не является алгоритмом, который решает проблему в этой области ввода / вывода ... что означает, что у вас нет алгоритма на все или что у вас есть только алгоритм, если вы соответствующим образом ограничиваете домен.

Answer 5

Да -

SortNumbers(collectionOfNumbers)
{
  If IsSorted(collectionOfNumbers){
     reverse(collectionOfNumbers(1:end/2))     
  } 

  return SortNumbers(collectionOfNumbers)
}

Answer 6

Как насчет этого:

1. Начните с первого предмета.
2. Переверните монету.
3. Если это головы, переключите ее на следующий предмет.
4. Если это хвосты, не переключайте их.
5. Если список отсортирован, остановитесь.
6. Если нет, переходите к следующей паре ...

Это алгоритм сортировки - то, что может сделать обезьяна.Есть ли гарантия, что вы попадете в отсортированный список?Я так не думаю!

Answer 7

Предположим, что у вас есть случайный флиппер, бесконечная арифметика и бесконечные рациональные числа. Тогда ответ - да. Вы можете написать алгоритм сортировки, который имеет 100% -ную вероятность успешной сортировки ваших данных (так что это действительно функция сортировки), но который в среднем займет бесконечное время.

Вот эмуляция этого в Python.

# We'll pretend that these are true random numbers.
import random
import fractions

def flip ():
    return 0.5 < random.random()

# This tests whether a number is less than an infinite precision number in the range
# [0, 1].  It has a 100% probability of returning an answer.
def number_less_than_rand (x):
    high = fractions.Fraction(1, 1)
    low = fractions.Fraction(0, 1)

    while low < x and x < high:
        if flip():
            low = (low + high) / 2
        else:
            high = (low + high) / 2

    return high < x

def slow_sort (some_array):
    n = fractions.Fraction(100, 1)
    # This loop has a 100% chance of finishing, but its average time to complete
    # is also infinite.  If you haven't studied infinite series and products, you'll
    # just have to take this on faith.  Otherwise proving that is a fun exercise.
    while not number_less_than_rand(1/n):
        n += 1
    print n
    some_array.sort()