Сложность времени: получение неверного результата - PullRequest
Новая
       121

Сложность времени: получение неверного результата

3 голосов
/ 01 мая 2020

Следующий код взят из книги «Взлом кодового интервью». Код печатает все перестановки строки.

Вопрос : Какова временная сложность кода ниже. 

void permutation(String str) {
    permutation(str, "");
}

private void permutation(String str, String prefix) {

    if (str.length() == 0){
        System.out.println(prefix);
    } else {
        for (int i = 0; i <str.length(); i++) {
            String rem = str.substring(0, i) + str.substring(i + 1);
            permutation(rem, prefix + str.charAt(i));
        }
    }
}

Мое понимание:

Я могу вывести сложность времени следующим образом: n * n!.

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

Может ли кто-нибудь поделиться некоторыми материалами, желательно с примерами?

enter image description here

Ответы [ 2 ]

3 голосов
/ 07 мая 2020

Вы очень на правильном пути, и ваша общая оценка (что время выполнения равно Θ (n · n!)) Верна! Один из методов, который мы можем использовать для определения времени выполнения, - это подвести итог, проделанную работу на каждом слое дерева. Мы знаем, что

  • в слое 0 (верхний слой), есть 1 узел, обрабатывающий строку длины n,
  • в слое 1, есть n узлов, каждая из которых обрабатывает строки длины n - 1,
  • на уровне 2, имеется n (n-1) узлов, каждая из которых обрабатывает строки длиной n - 2,
  • на уровне 3, существует n (n-1) (n-2) узлов каждой строки обработки длиной n -3,
  • ...
  • в слое n, существует n! каждая из узлов обрабатывает строки длиной 0.

Чтобы учесть общую работу, проделанную здесь, давайте предположим, что каждый рекурсивный вызов выполняет O (1) на базовой линии плюс работа, пропорциональная длине строки что это обработка. Это означает, что нам нужно вычислить две суммы для определения общей выполненной работы:

Сумма 1: Количество вызовов

1 + n + n (n-1) + n (n-1) (n-2) + ... + n!

и

Сумма 2: Строки обработки работ

1 · n + n · (n-1) + n (n-1) · (n-2) + ... + n! · 0

Но есть еще один фактор, который необходимо учитывать - каждый рекурсивный вызов, который попадает в базовый случай, выводит строку, созданную таким образом, что занимает O (n) времени. Так что это добавляет в конечном множителе · (n · n!). Таким образом, общая выполненная работа будет равна Θ (n · n!) Плюс работа, выполненная всеми промежуточными рекурсивными вызовами для построения ответов.

Давайте рассмотрим каждую из этих сумм индивидуально.

Сумма 1: Количество вызовов

Мы имеем дело с этой необычной суммой:

1 + n + n (n-1) + n (n-1) ( n-2) + ... + n!

Главное наблюдение, которое нам нужно, это то, что

  • 1 = n! / n!,
  • n = n! / (n-1)!,
  • n (n-1) = n! / (n-2)!
  • ...
  • n! = п! / (nn)!

Другими словами, эта сумма равна

n! / н! + п! / (n-1)! + п! / (n-2)! + ... + n! / 0!

= n! (1 / n! + 1 / (n-1)! + 1 / (n-2)! + ... + 1/0!)

≤ en!

= Θ (n!)

Здесь этот последний шаг следует из того факта, что сумма

1/0! + 1/1! + 1/2! + 1/3! + ...

до бесконечности - один из способов определения числа e. Это означает, что общее количество рекурсивных вызовов, сделанных здесь, составляет Θ (n!).

И, интуитивно, это должно иметь смысл. Каждый рекурсивный вызов, за исключением рекурсивных вызовов в строках длины один, выполняет два других рекурсивных вызова, поэтому дерево рекурсии в основном ветвится. И есть хороший факт о деревьях, который говорит, что дерево, где каждый узел ветвится, не будет иметь больше внутренних узлов, чем листьев. Так как есть n! уходит, не удивительно, что оставшееся количество узлов получается чем-то, что не асимптотически больше, чем n! *

1 · n + n · (n-1) + n (n-1) · (n-2) + ... + n! · 0

Мы можем переписать это как

n + n (n-1) + n (n-1) (n-2) + ...

и эй! Мы знаем эту сумму - почти буквально ту, которую мы только что видели. Это работает для Θ (n!).

Собираем все вместе

Подводя итог, этот рекурсивный алгоритм

  • Θ (n!) Работает просто из-за на количество рекурсивных вызовов, причем каждый вызов занимает некоторое базовое количество времени;
  • n (n!) работа, выполняемая рекурсивными вызовами, когда они формируют и объединяют подстроки; и
  • Θ (n · n!) работа, выполненная последними рекурсивными вызовами для распечатки всех перестановок.

Подводя итоги, вы получите Θ (n · n!) времени выполнения, которое вы предложили в своем вопросе.

Надеюсь, это поможет!

0 голосов
/ 02 мая 2020

Сложность времени будет O(n!). Вот анализ (скопировано с geeksforgeeks ). Он также известен как алгоритм кучи.

Анализ сложности:

  1. Алгоритм генерирует (n-1)! перестановок первых n-1 элементов, примыкающих к последним элемент к каждому из них. Это сгенерирует все перестановки, которые заканчиваются последним элементом.
  2. Если n нечетно, поменяйте местами первый и последний элемент, а если n чётно, то поменяйте местами элемент i ( счетчик, начинающийся с 0) и последний элемент, и повторяйте вышеуказанный алгоритм до тех пор, пока i не станет меньше n.
  3. На каждой итерации алгоритм будет генерировать все перестановки, которые заканчиваются текущим последним элементом.
...