Время выполнения для функции с циклом, включающим рекурсивные вызовы - PullRequest
Новая
       19

Время выполнения для функции с циклом, включающим рекурсивные вызовы

1 голос
/ 20 сентября 2019

Я выполняю следующую задачу:

Найдите временную сложность следующего кода: enter image description here

И мой мыслительный процессвыглядит следующим образом:

Просмотр работы, выполненной внутри каждого вызова permutation:

System.out.println(prefix); потребует O (n) времени

String rem = str.substring(0, i) + str.substring(i+1); такжезанять O (N) время.Это связано с тем, что для объединения двух строк требуется время O (m + n), где m и n - длина строки.Поскольку в этом случае длины всегда составляют n, это будет всего O (n).

Наконец, фактический вызов permutation (пока не рекурсия) и оператор str.charAt(i)будет сделано в постоянное время, поэтому O (1).

Однако меня смущает тот факт, что это делается в цикле.В моей книге решение объясняется как «Каждый узел в нашем дереве вызовов, следовательно, соответствует O (n) work».Разве каждый узел не будет работать за O (n + n ^ 2) = 0 (n ^ 2), поскольку каждая итерация цикла работает за O (n), и он будет вызываться n раз?

Поэтому, подумав об этом пару раз, я решил перефразировать мой вопрос в более общем смысле: как бы вы оценили сложность времени для функции такого типа стандартизированным способом (метод, который можно применить к большинству, если нет?все проблемы такого характера)?Хотя простое рассуждение по ситуации работает, оно также склонно к неправильным представлениям (как я продемонстрировал), так есть ли более общий способ сделать это?

1 Ответ

0 голосов
/ 20 сентября 2019

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

Итак, сначала, приближаясь к этому сценарию, мы начнем с рассмотрения работы внутри каждого вызова permutation:

  • System.out.println(prefix); -> O (n)
  • String rem = str.substring(0, i) + str.substring(i+1); -> O (n)
  • permutation(rem, prefix+str.charAt(i)); -> O (1) [этопока не учитывает рекурсию !!!]

Итак, теперь мы знаем объем работы, выполненной внутри каждого узла в общем дереве вызовов.Теперь рассмотрим рекурсию.Есть два разных способа думать об этом.

1) Рекурсия в сочетании с циклом

Поскольку и цикл, и рекурсивный вызов приводят к вызову permutation, мы можем просто беспокоиться ообщее количество вызовов permutation, а не различие между циклом и обычными рекурсивными вызовами.Таким образом, мы берем пример строки, скажем, 'abc' и исследуем листовые узлы дерева вызовов:

  1. 'abc' -> 1 узел
  2. 'a', 'b',' c '-> 3 узла
  3. ' ab ',' ac ',' ba ',' bc ',' ca ',' cb '-> 6 узлов

Таким образом, мы видим, что у нас есть 6 листовых узлов.Сразу видно, что это равно 3!где 3 - длина нашей входной строки 'abc'.Таким образом, количество листовых узлов будет n!, где n соответствует длине входной строки.Глубина дерева вызовов всегда будет n, так как рекурсия останавливается, когда n=0.Таким образом, общее количество узлов в нашем дереве вызовов будет n*n!.Поскольку каждый узел соответствует O(n) работе, наша общая выполненная работа составляет O(n x n x n!) = O((n + 2)!) [мы можем сделать это, потому что можем отбрасывать константы!].

2) Рекурсия отдельно от цикла

ТеперьВот где мое замешательство, и поэтому этот вопрос возник.Казалось логичным, что работа, выполняемая в каждом узле, будет O(n^2), а не O(n), поскольку цикл for находится внутри узла, верно?В этом случае я думал о цикле for и рекурсии как об отдельных объектах.Но этот способ мышления не совсем корректен, потому что цикл for не просто запускается n раз при каждом вызове, скорее, он запускается n раз, затем n-1 раз, затем n-2,и т. д. В общей сложности он запускается n! раз каждый раз, когда запускается .Таким образом, у нас есть n! прогонов, каждый раз выполнение O(n) означает, что в общей сложности O(n x n!) запусков после запуска.Но теперь мы только рассмотрели, сколько раз цикл for запускается каждый раз, когда он вызывается.Сколько раз это на самом деле началось?Что ж, это будет n раз, потому что мы можем видеть, что рекурсия заканчивается, когда n=0.Следовательно, n x n x n! еще раз.

Теперь, если вы обнаружите ошибку в моих рассуждениях (особенно со вторым способом мышления), пожалуйста, не стесняйтесь указывать на это!Я хочу убедиться, что я думаю об этом правильно.

...