Вопрос по runtime, big-o, algorithm – Big-O Нотация относительно логарифмов

3

Мне задали вопрос на собеседовании, в котором я хотел различить обозначение Big-O нескольких логарифмических функций. Функции были следующими:

f (x) = log5(Икс)

f (x) = log (x5)

f (x) = log (6 * log x)

f (x) = log (log x)

Мне сказали, что Big-O для первого и второго не эквивалентны, а третий и четвертый не эквивалентны после ошибочного предположения об обратном. Кто-нибудь может объяснить, почему они не эквивалентны и каковы их Big-O?

Извините за опечатку, все они зависят от х, была исправлена. <SUP> был добавлен для ясности. Извините всех за путаницу. user1246462
Просто чтобы уточнить: четыре журналаSUP> 5 </ SUP>х, лог (х <SUP> 5 </ SUP>), log (6 log x), log log x? (используя <SUP> теги вполне намеренно) nneonneo
Действительно, нотация big-O пригодится для границ аппроксимации в анализе, в котором вы обычно имеете дело с непрерывными переменными. nneonneo

Ваш Ответ

4   ответа
0

f(n)неf(x), За 1 и 2log^5(n) эквивалентноO(log log log log log(n)), в то время как .log(n^5) = 5 log(n) = O(log n)

Для 3 и 4 я не согласен.log(6*log n) = log(6) + log(log n) = O(log log n), что так же, как 4 -.O(log log n)

О, хорошо, мы получили те же ответы. nneonneo
1
f(x) = log^5(n)
f(x) = log(n^5) -> 5 log(n)
O(5 log(n)) < O(log(n)^5)

f(x) = log(6*log n) -> log(6)+log(log(n))
f(x) = log(log n) 
log(log n) < log(6) + log(log(n)) 

поэтому они имеют одинаковый OI '

2

f (x) = log5(Икс)f (x) = log (x5) = 5 * log xf (x) = log (6 * log x) = log 6 + log (log x)f (x) = log (log x)

Так что Большой О

O (log5(Икс))O (log x)O (log (log x))O (log (log x))

Так (1) и (2) не 'т, но (3) и (4) (хотя ониотличается от обоих (1) и (2)

4
log5 х - это то же самое, что запись журнала.очень медленно растущая функция х.Это эквивалентно 5 log x (переписывание возведения в степень внутри журнала как умножения снаружи), что эквивалентно log x.Это эквивалентно log 6 + log log x, что эквивалентно log log x.Это просто лог лог х.

у вас есть O (log log log log x), O (log x), O (log log x) и O (log log x), три разных класса Big-O.

Если ваш интервьюер сказал, что 3 и 4 были разными, он либо ошибся, либо выМы неправильно запомнили вопрос (происходит постоянно).

2. должно быть 5 * log x, а не log 5 + log x (хотя в этом случае они имеют одинаковый порядок). Yuushi
log (x) ^ 5, таким образом, будет демонстрировать более быстрый рост, чем log ^ 5x? user1246462
Намного быстрее. log ^ 5 x растет медленнее, чем log ^ 4 x, который растет медленнее, чем log (x), который медленнее, чем log (x) ^ 5. nneonneo
Я нахожу такой способ интерпретации log ^ 5 (x) наиболее необычным. Хотя в алгебре используются обозначения типа f ^ 5 (x) для 5 вложенных приложений от f к x, я неЯ думаю, что это обычно делается в контексте информатики. Я'принять это значение (log x) ^ 5. jogojapan

Похожие вопросы