Результаты поиска

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

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

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

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

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

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]