Завтра у меня среднесрочный курс по информатике, и мне нужна помощь в определении сложности этих рекурсивных функций. Я знаю, как решать простые случаи, но я все еще пытаюсь научиться решать эти сложные случаи. Это были лишь некоторые из примеров проблем, которые я не мог понять. Любая помощь будет высоко ценится и очень поможет в моей учебе, спасибо!
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf("%d, %d\n",m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
}
recursion
big-o
complexity-theory
Michael_19
источник
источник
Ответы:
Временная сложность в обозначениях Big O для каждой функции находится в числовом порядке:
O(n)
часто называют линейной .O(n)
. (На самом деле называется порядок n / 5 раз. И, O (n / 5) = O (n)).O(log(n))
(основание 5), часто называемое логарифмическим и чаще всего анализом обозначений и сложности Big O, использует основание 2.O(2^n)
или экспоненциально , так как каждый вызов функции вызывает себя дважды, если только он не был повторен n раз.Что касается последней функции, цикл for принимает n / 2, так как мы увеличиваем на 2, а рекурсия - n-5, и поскольку цикл for вызывается рекурсивно, следовательно, сложность времени находится в (n-5) * (n / 2) = (2n-10) * n = 2n ^ 2-10n, из-за асимптотического поведения и соображений сценария наихудшего случая или из-за верхней границы, к которой стремится большой O, нас интересует только самый большой член
O(n^2)
.Удачи на ваших промежуточных условиях;)
источник
n/2
итерациямfor
цикла, почему уменьшение на 5 не приведет кn/5
рекурсивным вызовам? Это все равно приведет к,O(n^2)
но кажется более интуитивным объяснением. Зачем смешивать вычитание и деление, если они необходимы, делая одно и то же?n/5
неn-5
. И в конечном итоге все сводится кO(N^2)
.Для случая , когда
n <= 0
,T(n) = O(1)
. Следовательно, сложность времени будет зависеть от того, когдаn >= 0
.Мы рассмотрим случай
n >= 0
в части ниже.1.
где а - некоторая постоянная
По индукции:
где a, b - некоторая константа.
2.
где а некоторая постоянная
По индукции:
где a, b некоторая постоянная и k <= 0
3.
где а некоторая постоянная
По индукции:
где a, b некоторая постоянная
4.
где а некоторая постоянная
По индукции:
где a, b - некоторая константа.
5.
где n - некоторая постоянная
Перепишите,
n = 5q + r
где q и r являются целыми числами, а r = 0, 1, 2, 3, 4Мы имеем
q = (n - r) / 5
, и так как г <5, мы можем считать его константой, поэтомуq = O(n)
По индукции:
Поскольку r <4, мы можем найти некоторую константу b так, чтобы
b >= T(r)
источник
Один из лучших способов аппроксимации сложности рекурсивного алгоритма, который я нашел, - это построение дерева рекурсии. Когда у вас есть рекурсивное дерево:
n
и номер конечного узла,1
поэтому сложность будетn*1 = n
Вторая функция снова будет иметь длину
n/5
и количество конечных узлов,1
поэтому сложность будетn/5 * 1 = n/5
. Это должно быть приближено кn
Для третьей функции, поскольку
n
она делится на 5 при каждом рекурсивном вызове, длина рекурсивного дерева будет равнаlog(n)(base 5)
, а число конечных узлов снова 1, поэтому сложность будетlog(n)(base 5) * 1 = log(n)(base 5)
Для четвертой функции, поскольку каждый узел будет иметь два дочерних узла, число конечных узлов будет равно,
(2^n)
а длина рекурсивного дерева будетn
такой же сложной(2^n) * n
. Но посколькуn
он незначителен перед ним(2^n)
, его можно игнорировать, а сложность можно только сказать(2^n)
.Для пятой функции есть два элемента, представляющих сложность. Сложность, обусловленная рекурсивной природой функции, и сложность, введенная
for
циклом в каждой функции. При выполнении вышеприведенного вычисления сложность, обусловленная рекурсивным характером функции, будет~ n
и сложностью из-за цикла forn
. Общая сложность будетn*n
.Примечание. Это быстрый и грязный способ вычисления сложности (ничего официального!). Хотелось бы услышать отзывы об этом. Спасибо.
источник
2^n
высота дерева должна бытьn
, а неlog n
. Высота будет только в томlog n
случае, еслиn
представлено общее количество узлов в дереве. Но это не так.Мы можем доказать это математически, чего мне не хватало в приведенных выше ответах.
Это может существенно помочь вам понять, как рассчитать любой метод. Я рекомендую прочитать это сверху вниз, чтобы полностью понять, как это сделать:
T(n) = T(n-1) + 1
Это означает, что время, необходимое для завершения метода, равно тому же самому методу, но с n-1, которыйT(n-1)
мы сейчас и добавим,+ 1
потому что это время, которое требуется для выполнения общих операций (кромеT(n-1)
). Теперь мы собираемся найтиT(n-1)
следующим образом :T(n-1) = T(n-1-1) + 1
. Похоже, что теперь мы можем сформировать функцию, которая может дать нам какое-то повторение, чтобы мы могли полностью понять. Мы разместим с правой стороны ,T(n-1) = ...
а неT(n-1)
внутри метода ,T(n) = ...
который даст нам:T(n) = T(n-1-1) + 1 + 1
что являетсяT(n) = T(n-2) + 2
или другими словами , мы должны найти наш отсутствующийk
:T(n) = T(n-k) + k
. Следующим шагом является принятиеn-k
и утверждение, что,n-k = 1
поскольку в конце рекурсии потребуется ровно O (1), когдаn<=0
, Из этого простого уравнения мы теперь знаем этоk = n - 1
. Давайте поместимk
в наш последний метод:T(n) = T(n-k) + k
который даст нам:T(n) = 1 + n - 1
который точноn
илиO(n)
.O(n)
.T(n) = T(n/5) + 1
как и раньше, время завершения этого метода равно времени того же метода, но сn/5
которым он ограниченT(n/5)
. Давайте найдемT(n/5)
как в 1:T(n/5) = T(n/5/5) + 1
что естьT(n/5) = T(n/5^2) + 1
. Давайте местоT(n/5)
внутриT(n)
для окончательного расчета:T(n) = T(n/5^k) + k
. Опять же, как и раньше,n/5^k = 1
чтоn = 5^k
это именно так , спрашивая , что в силе 5, даст нам п, ответlog5n = k
(журнал базы 5). Поместим наши выводы вT(n) = T(n/5^k) + k
следующим образом :T(n) = 1 + logn
чтоO(logn)
T(n) = 2T(n-1) + 1
то, что мы имеем здесь, в основном то же, что и раньше, но на этот раз мы вызываем метод рекурсивно 2 раза, таким образом, мы умножаем его на 2. Давайте найдем,T(n-1) = 2T(n-1-1) + 1
что естьT(n-1) = 2T(n-2) + 1
. Наше следующее место, как и прежде, давайте разместим наш вывод:T(n) = 2(2T(n-2)) + 1 + 1
что этоT(n) = 2^2T(n-2) + 2
нам даетT(n) = 2^kT(n-k) + k
. Давайте найдемk
, утверждая,n-k = 1
что естьk = n - 1
. Разместимk
следующим образом:T(n) = 2^(n-1) + n - 1
что примерноO(2^n)
T(n) = T(n-5) + n + 1
Это почти то же самое, что 4, но теперь мы добавляем,n
потому что у нас есть одинfor
цикл. Давайте найдемT(n-5) = T(n-5-5) + n + 1
что естьT(n-5) = T(n - 2*5) + n + 1
. Поместим его:T(n) = T(n-2*5) + n + n + 1 + 1)
чтоT(n) = T(n-2*5) + 2n + 2)
и для к:T(n) = T(n-k*5) + kn + k)
снова:n-5k = 1
что является ,n = 5k + 1
что примерноn = k
. Это даст нам:T(n) = T(0) + n^2 + n
что примерноO(n^2)
.Теперь я рекомендую прочитать остальные ответы, которые сейчас дадут вам лучшую перспективу. Удачи, выиграв эти большие O :)
источник
Ключевым моментом здесь является визуализация дерева вызовов. После этого сложность такова:
последний член может быть вычислен так же, как и для обычной итерационной функции.
Вместо этого общие узлы полного дерева вычисляются как
Где C - количество дочерних элементов каждого узла, а L - количество уровней дерева (включая корень).
Это легко визуализировать дерево. Начните с первого вызова (корневого узла), затем нарисуйте количество дочерних элементов, равное количеству рекурсивных вызовов в функции. Также полезно записать параметр, переданный во вспомогательный вызов, как «значение узла».
Итак, в приведенных выше примерах:
источник