#big-o #computer-science
#big-o #информатика
Вопрос:
Я уже несколько дней пытаюсь решить вопрос. Я искал в Интернете справку, и единственный ответ, который я нашел, противоположен моему выводу.
Вот вопрос:
**3^n = 2^(O(n)) True or False?**
Вывод «ИСТИННЫЙ», и правильный ответ:
3^n = 2^(O(n)) since 3^n = 2^(n*log_2(3)) = 2^(O(n))
Проблема в том, что я понятия не имею, как был определен ответ. Пошаговый процесс был бы лучшим объяснением для меня. Другими словами, как было преобразовано 3 ^ n = 2 ^ n в журнал, как мы определили как константу, так и начальную точку, где n > = k?
Редактировать: Может быть, было бы проще объяснить, откуда берутся 2 и 3 в этом обоснованном предположении.Решение имеет ОДИН 3 и ДВА 2.
If f(n) = 3^n and g(n) = 2^n
The 3 in 2^(n*log_2(3)) must be coming from f(n)?
The 2 in 2^(n*log_2(3)) must be coming from g(n)'s base?
----> Is the log_2 a constant??
Другими словами, если вопрос был
7^n = 4^(O(n)) ?
Правильный ответ был бы
4^(n*log_2(7))
How is k determined, where all n >= k?
Заранее спасибо!!!
Комментарии:
1. ваш профессор прав (что неудивительно!). что вы не понимаете в его рассуждениях?
2. Это не мой профессор xD. Мой профессор вообще не говорил об этом. Наверное, я вообще не понимаю их ответа или почему мой неправильный. Согласно книге, мой ответ должен быть правильным, верно? Чего мне не хватает?
3. ваши рассуждения неверны, потому что вы выбираете константу «c» «неправильным способом». вы находите ‘c’, для которого при n> N выполняется выражение true
4. Вы уверены? Потому что, если это так, то почему в вопросе задается вопрос «true или false?», Если вы можете получить только истинный ответ? В противном случае, можете ли вы объяснить их ответ? Я понятия не имею, как они пришли к этому ответу. Заранее спасибо!
5. en.wikipedia.org/wiki/Time_complexity#Exponential_time может быть полезно в качестве еще одной ссылки здесь.
Ответ №1:
Профессор прав. Их логика такова: 3^n = (2^log_2(3))^n = 2^(n*log_2(3)) = 2^O(n)
log_2(3) = z означает «2 в степени z дает мне 3», и мы повышаем 2 до этого показателя, поэтому получаем 3^n .
В основном они показали, что, умножив показатель степени на 2^x константу, вы можете изменить базу на 3. Big O отбрасывает константы, поэтому не имеет значения, равно ли основание 2 или 3.
Редактировать:
If f(n) = 3^n and g(n) = 2^n
The 3 in 2^(n*log_2(3)) must be coming from f(n)?
The 2 in 2^(n*log_2(3)) must be coming from g(n)'s base?
----> Is the log_2 a constant??
Я не уверен, что вы пытаетесь спросить здесь. log_2 постоянного числа является константой.
4^(n*log_2(7))
Where k = 7, and n >= 7 and 2 is the constant 'c'?
Ваш «ответ» должен быть 7^n = 4^O(n) . Ваш способ показать это 7^n = 4^(n*log_4(7)) = 4^O(n) , как 4^log_4(7) = 7 .
Комментарии:
1. На самом деле я удалил его, не уверен, правильно ли это, потому что кажется, что это то, что вы должны делать, основываясь на этой цитате из учебника об экспонентах. @FoxDonut Я пытаюсь разобраться в этом сейчас.
2. Да, я думаю, вы смотрели на случайную константу, которую я выбрал, лол
3. Я был бы очень признателен за это. Кажется действительно странным, что я мог быть НАСТОЛЬКО далек, следуя примеру книги. Проблема в том, что у меня нет доступа к ответу. Если хотите, я могу сфотографировать текст, чтобы вы могли видеть весь абзац.
4. Ваше определение для Big O является неполным. Вам нужно выбрать достаточно высокую начальную точку. Посмотрите на это: en.m.wikipedia.org/wiki/Big_O_notation#Formal_definition . Эта картинка также может помочь, обратите внимание, что cg(n) становится верхней границей только после некоторой точки k: xlinux.nist.gov/dads/Images/bigOGraph.gif
5. Я добавил абзац. К сожалению, это вся информация, которая приведена в главе об этой теме. Я посмотрю на предоставленную вами ссылку. Кроме того, если f (n) не ВСЕГДА равно O(g (n)), то не будет ли ответ ложным? Вы сказали, что это было только после определенного момента, верно?