Вопрос по big-o, runtime, 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?

Действительно, нотация big-O пригодится для границ аппроксимации в анализе, в котором вы обычно имеете дело с непрерывными переменными. nneonneo
Извините за опечатку, все они зависят от х, была исправлена. & Л; вечерять & GT; был добавлен для ясности. Извините всех за путаницу. user1246462
Просто для пояснения: четыре - это log & sup; 5 & sup & x; x, log (x & sup; 5 & sup; / sup & gt;), log (6 log x), log log x? (используя теги & lt; sup & gt; преднамеренно) nneonneo

Ваш Ответ

4   ответа
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)) 

хотя log (6) является константой, поэтому они имеют одинаковую O

4
log5 x is the same as writing log log log log log x, which is a very slow-growing function of x. This is equivalent to 5 log x (rewriting exponentiation inside the log as multiplication outside), which is equivalent to log x. This is equivalent to log 6 + log log x, which is equivalent to log log x. This is just 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 (хотя в этом случае они имеют одинаковый порядок).
И log & lt; sup & gt; 5 & sup & xt; x не эквивалентен (logx) & lt; sup & lt; 5 & sup & gt; правильный? user1246462
Да ты прав. Я неправильно прочитал ... думал, что это журнал (5x) по какой-то причине.
Да, это правильно. log ^ 5 - это 5 повторных приложений журнала; log (x) ^ 5 - это log (x) для пятой степени. Они разных порядков.
Я нахожу такой способ интерпретации log ^ 5 (x) наиболее необычным. Хотя в алгебре используются такие обозначения, как f ^ 5 (x) для 5 вложенных приложений от f к x, я не думаю, что это обычно делается в контексте информатики. Я полагаю, что это означает (log x) ^ 5.
2

Это вопрос математики:

f(x) = log5(x) f(x) = log(x5) = 5 * log x f(x) = log(6*log x) = log 6 + log(log x) f(x) = log(log x)

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

O(log5(x)) O(log x) O(log (log x)) O(log (log x))

Таким образом, (1) и (2) не эквивалентны, но (3) и (4) (хотя они отличаются от (1) и (2))

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).

О, хорошо, мы получили те же ответы.

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