Намиране на Big Theta

Аз съм в клас по структури от данни и алгоритми. Опитвам се да посоча дали f(n) е Голямата тета на g(n). Ще трябва също да посоча голямо O, малко o и т.н., но съм загубен относно начина, по който да подходя към тази конкретна двойка.

f(n) = log* (log n)
g(n) = log( log* n )

От това, което научих в момента, ако тази двойка завърши това твърдение

Θ(g(n))={f(n):there exists c_1, c_2 > 0 and n_0 <br>
 such that 0 ≤ c_1 g(n) ≤ f(n) ≤ c_2 g(n) for all n ≥ n_0}.

Проблемът ми е, че нямам представа какво е log * и как да го използвам.


recurrence algorithm notation
person user3339453    schedule 22.02.2014    source източник
comment
Не мисля, че това е програмен въпрос. Попитайте това на сайта за математика.   -  person Mark    schedule 22.02.2014

Отговори (1)


arrow_upward
0
arrow_downward

Нямам представа какво е log *

Е, вижте го. За съжаление Google не търси много добре символи, но търсенето в Google log star показва итериран логаритъм незабавно и SymbolHound, търсачка, която не пренебрегва символите, показва Публикация на StackOverflow, която го обяснява. Също така вероятно е някъде във вашата книга или бележки за курса.

Повтарящият се логаритъм, означен като log*(n), е броят пъти, които трябва да вземете логаритъм от n, преди да получите стойност, по-малка или равна на 1.

За да разрешите проблема, помислете за следното. Ако трябва да вземете логаритъм от n log*(n) пъти, преди да получите стойност ‹= 1, колко пъти трябва да вземете логаритъм от log(n), за да направите същото?

person user2357112 supports Monica    schedule 22.02.2014
comment
И така... за да посочим дали f(n) е Голямата тета на g(n). Дали алгебрата при решаването му ще бъде същата като всяка друга задача на log base x? - person user3339453; 22.02.2014
comment
@user3339453: Не съвсем същото, но доста подобно. Имайте предвид, че log* не е логаритъм, така че не можете да приложите към него обичайните равенства за логаритми. - person user2357112 supports Monica; 22.02.2014