Big-O анализ перестановочного алгоритма - PullRequest
Новая
       7

Big-O анализ перестановочного алгоритма

0 голосов
/ 03 февраля 2019 
result = False
def permute(a,l,r,b):
    global result
    if l==r:
        if a==b:
            result = True
    else:
        for i in range(l, r+1):
            a[l], a[i] = a[i], a[l]
            permute(a, l+1, r, b)
            a[l], a[i] = a[i], a[l]

string1 = list("abc")
string2 = list("ggg")
permute(string1, 0, len(string1)-1, string2)

Так что, в принципе, я думаю, что для поиска каждой перестановки требуется n ^ 2 шага (умножить на некоторую постоянную), а для поиска всех перестановок нужно n!шаги.Так это делает это O (n ^ 2 * n!)?и если это так, то n!взять на себя, делая его просто O (n!)?

Спасибо

edit: этот алгоритм может показаться странным только для поиска перестановок, и это потому, что я также использую его для проверки наанаграммы между двумя строками.Я просто еще не переименовал метод, извините

1 Ответ

0 голосов
/ 03 февраля 2019

Нахождение каждой перестановки не занимает O(N^2).Создание каждой перестановки происходит за O(1) время.Хотя заманчиво сказать, что это O(N), поскольку вы назначаете новый элемент каждому индексу N раз на перестановку, каждая перестановка делит назначения с другими перестановками.

Когда мы делаем: 

a[l], a[i] = a[i], a[l]
permute(a, l+1, r, b)

Все последующие рекурсивные вызовы permute на линии имеют это назначение уже на месте.

В действительности, назначения происходят только каждыйвремя permute называется, то есть enter image description here раз.Затем мы можем определить сложность времени для построения каждой перестановки, используя некоторое предельное исчисление.Мы берем количество назначений за общее число перестановок, когда N приближается к бесконечности.

Имеется:

enter image description here

Расширение сигмы:

enter image description here

Лимит суммы является суммой лимитов:

enter image description here

На данный момент мы оцениваем наши лимиты и все условиякроме первого обвала до нуля.Поскольку наш результат является константой, мы получаем, что наша сложность для каждой перестановки равна O(1).

enter image description here

Однако мы забываем об этой части:

if l==r:
    if a==b:
        result = True

Сравнение a == b (между двумя списками) происходит в O(N).Построение каждой перестановки занимает O(1), но наше сравнение в конце, которое происходит для каждой перестановки, на самом деле занимает O(N).Это дает нам временную сложность O(N) для каждой перестановки.

Это дает вам N! раз перестановок O(N) для каждой перестановки, что дает вам общую временную сложность O(N!) * O(N) = O(N * N!).

Ваша окончательная временная сложность не уменьшается до O(N!), поскольку O(N * N!) все еще на порядок больше O(N!), и отбрасываются только постоянные члены (та же причина, по которой O(NlogN) != O(N)).

...