В поисках большой теты

Я в классе структур данных и алгоритмов. Я пытаюсь указать, является ли f (n) большой тета g (n). Мне также нужно будет указать большое О, маленькое О и т. д., но я не знаю, как подойти к этой конкретной паре.

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
Я не думаю, что это вопрос программирования. Спросите об этом на сайте Math.   -  person Mark    schedule 22.02.2014

Ответы (1)


arrow_upward
0
arrow_downward

Я понятия не имею, что такое журнал *

Ну, посмотри. К сожалению, 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). Будет ли алгебра при ее решении такой же, как и в любой другой задаче с логарифмической базой x? - person user3339453; 22.02.2014
comment
@ user3339453: Не совсем то же самое, но очень похоже. Обратите внимание, что log* не является логарифмом, поэтому к нему нельзя применить обычные равенства для логарифмов. - person user2357112 supports Monica; 22.02.2014