Доказательство алгоритмов с помощью логарифмов

Я знаю, как доказывать алгоритмы, но не знаю, как доказывать экспоненциальные и логарифмические алгоритмы:

Ex: Given f(n) = 1.05^n and g(n) = n^2, determine if f(n)=O(g(n))

Ex: Given f(n) = (log-base4 of n) and g(n) = (log-base2 of n), determine if f(n)=bigTheta(g(n))

Ex: Given f(n) = 4^n, and g(n) = 2^n, determine if f(n)=O(g(n)).

Я не ищу решения (хотя я был бы не против подробного примера), а скорее объяснение того, как решать такие проблемы. Те, которые я упомянул выше, - это несколько разных, с которыми я столкнулся и которые меня смущают.


analysis algorithm big-o logarithm
person Shaku    schedule 18.01.2014    source источник
comment
Я обнаружил, что большинство таких задач решается по индукции, когда вы доказываете тривиальный случай (n = 1); считать истинным для всех от n до x; затем докажите x+1, переставив члены так, чтобы вы получили свой n случай и свой базовый случай.   -  person hd1    schedule 18.01.2014
comment
Я ищу другой, более прямой способ доказать это. (Например, решение c1, c2, n0)   -  person Shaku    schedule 18.01.2014

Ответы (1)


arrow_upward
2
arrow_downward

Асимптотически n! >> aⁿ >> nᵃ >> nlogn >> n >> logn >> a (константа).
Итак, если f=1,5ⁿ=aⁿ и g=n²=nᵃ, вы можете видеть, что f >> g для достаточно большое значение n.
Итак, g=O(f) и f=Ω(g), асимптотически.

Точно так же f=log₂n >> g=log₄n, поэтому f=Ω(g).

И 4ⁿ >> 2ⁿ. Итак, если f = 4ⁿ и g = 2ⁿ, f = Ω (g).

person tanmoy    schedule 18.01.2014
comment
Однако это не доказательство, которое ищет ОП. - person phant0m; 18.01.2014