Временная сложность программы с использованием уравнения рекуррентности

Ответ 1

Хорошо, мне кажется, что я смог доказать, что f(x) = Theta(2^x) (обратите внимание, что временная сложность такая же). Это также доказывает, что g(x) = Theta(2^x) как f(x) > g(x) > f(x-1).

Сначала, как отметили все, легко доказать, что f(x) = Omega(2^x).

Теперь мы имеем отношение, что f(x) <= 2 f(x-1) + f(x/2) (так как f(x) > g(x))

Покажем, что при достаточно больших x существует некоторая константа K > 0 такая, что

f(x) <= K*H(x), where H(x) = (2 + 1/x)^x

Отсюда следует, что f(x) = Theta(2^x), как H(x) = Theta(2^x), что само следует из того факта, что H(x)/2^x -> sqrt(e) as x-> infinity (wolfram alpha ссылка предел).

Теперь ( предупреждение: более тяжелая математика, perhap cs.stackexchange или math.stackexchange лучше подходит)

в соответствии с wolfram alpha (щелкните ссылку и посмотрите расширение серии рядом с x = бесконечность),

H(x) = exp(x ln(2) + 1/2 + O(1/x))

И опять же, согласно wolfram alpha (нажмите ссылку (отличную от предыдущей) и посмотрите разложение серии для x = бесконечность), мы что

H(x) - 2H(x-1) = [1/2x + O(1/x^2)]exp(x ln(2) + 1/2 + O(1/x))

и поэтому

[H(x) - 2H(x-1)]/H(x/2) -> infinity as x -> infinity

Таким образом, при достаточно больших x (скажем, x > L) имеет место неравенство

H(x) >= 2H(x-1) + H(x/2)

Теперь существует некоторая K (зависящая только от L (например, K = f (2L))) такая, что

f(x) <= K*H(x) for all x <= 2L

Теперь мы продолжим (сильную) индукцию (вы можете вернуться к натуральным числам, если хотите)

f(x+1) <= 2f(x) + f((x+1)/2)

По индукции правая часть

<= 2*K*H(x) + K*H((x+1)/2)

И мы ранее доказали, что

2*H(x) + H((x+1)/2) <= H(x+1)

Таким образом, f(x+1) <= K * H(x+1)

Ответ 2

Используя memoisation, обе функции могут быть легко вычислены в O (n) времени. Но программа занимает не менее O (2 ^ n) времени и, следовательно, является очень неэффективным способом вычисления f(n) и g(n)

Чтобы доказать, что программа принимает не более O (2 + epsilon) ^ n время для любого epsilon > 0:

Пусть F (n) и G (n) - число вызовов функций, которые выполняются при оценке f (n) и g (n) соответственно. Ясно (подсчет добавления как 1 вызов функции):

F (0) = 1; F (n) = F (n-1) + G (n) + 1 G (1) = 1; G (n) = F (n-1) + G (n/2) + 1

Тогда можно доказать:

• F и G монотонны
• F > G
• Определить H (1) = 2; H (n) = 2 * H (n-1) + H (n/2) + 1
• ясно, H > F
• для всех n, H (n) > 2 * H (n-1)
• поэтому H (n/2)/H (n-1) → 0 при достаточно больших n
• следовательно, H (n) (2 + epsilon) * H (n-1) для всех epsilon > 0 и достаточно больших n
• поэтому H в O ((2 + epsilon) ^ n) для любого epsilon > 0
• (Edit: изначально я пришел к выводу, что верхняя граница O (2 ^ n). Это неверно, как указал nhahtdh, но см. ниже)
• так что это лучшее, что я могу доказать.... Поскольку G < F < H они также находятся в O ((2 + epsilon) ^ n) для любого epsilon > 0

Постскриптум (после просмотра решения г-на Кноукса): Поскольку i.m.h.o хорошее математическое доказательство дает представление, а не множество формул, и SO существует для всех этих будущих поколений (привет!):

Для многих алгоритмов вычисление f (n + 1) включает в себя дважды (трижды,...) объем работы для f (n), плюс нечто большее. Если это больше становится относительно меньше с ростом n (что часто бывает), используя фиксированный epsilon, как указано выше, не является оптимальным. Замена эпсилона выше некоторой убывающей функцией ε (n) of n будет во многих случаях (если ε будет достаточно быстро убывать, скажем, ε (n) = 1/n), получим верхнюю грань O ((2 + ε (n)) ^ n) = O (2 ^ n)

Ответ 3

Пусть f (0) = 0 и g (0) = 0

Из функции мы имеем

f(x) = f(x - 1) + g(x) 
g(x) = f(x - 1) + g(x/2)

Подставляя g (x) в f (x), получим:

f(x) = f(x-1) + f(x -1) + g(x/2)

& there4; f (x) = 2f (x-1) + g (x/2)

Разлагая это, получим:

f(x) = 2f(x-1)+f(x/2-1)+f(x/4-1)+ ... + f(1)

Пусть s (x) - функция, определенная следующим образом:

s(x) = 2s(x-1)

Теперь ясно, что f (x) = & Omega; (s (x)).

Сложность s (x) равна O (2 ^x).

Поэтому функция f (x) = & Omega; (2 ^x).

Ответ 4

Я думаю, ясно, что f (n) > 2 ⁿ так как f (n) > h (n) = 2h (n-1) = 2 ⁿ.

Теперь я утверждаю, что для каждого n существует & epsilon; такой, что: f (n) (2 + & epsilon;) ⁿ, чтобы увидеть это, позвольте сделать это по индукции, но чтобы сделать его более разумным сначала, я буду использовать & epsilon; = 1, чтобы показать f (n) <= 3 ⁿ тогда я продолжу его.

Мы будем использовать сильную индукцию, пусть для каждого m < n, f (m) 3 ^m то имеем:

f(n) = 2[f(n-1) + f(n/2 -1) + f(n/4 -1)+ ... +f(1-1)]

но для этой части:

A = f(n/2 -1) + f(n/4 -1)+ ... +f(1-1)

имеем:

f(n/2) = 2[f(n/2 -1) + f(n/4 -1)+ ... +f(1-1]) ==>

A <= f(n/2)   [1]

Итак, мы можем переписать f (n):

f(n) = 2f(n-1) + A < 2f(n-1) +f(n/2),

Теперь вернемся к нашему утверждению:

f(n) < 2*3^(n-1) + 2*3^(n/2)==>
f(n) < 2*3^(n-1) + 3^(n-1) ==>
f(n) < 3^n.  [2]

В силу [2] доказательство f (n) & in; O (3 ⁿ) завершено.

Но если вы хотите распространить это на формат (2 + & epsilon;) ⁿ просто используйте 1, чтобы заменить неравенство, то мы будем иметь

для & epsilon; > 1/(2 + & epsilon;) ^n/2-1 → f (n) (2 + & эпсилон;). ^п [3]

Также в [3] вы можете сказать, что для каждого n существует & epsilon; такой, что f (n) (2 + & epsilon;) ⁿ на самом деле существует постоянный & epsilon; такой, что при n > n ₀ f (n) & in; O ((2 + & epsilon;) ⁿ). [4]

Теперь мы можем использовать wolfarmalpha как @Knoothe, установив & epsilon; = 1/n, тогда мы получим:

f (n) (2 + 1/n) ⁿ что приводит к f (n) e * 2 ⁿ а по нашей простой нижней границе в начале мы имеем: f (n) & in; & Theta;. (2 ^ п) [5]

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