Почему асимптотическая связь между lgn и log8n эквивалентна тому, что logn равен Θ(log8n)?

Я пытаюсь понять правильный ответ на следующий вопрос:

скриншот вопроса

Ответ заключался в том, что все они были верны, потому что lgn можно назвать тета log8n, который включает в себя все три варианта.

Это сбивает меня с толку, потому что для любого положительного значения n logn будет больше, чем log8n, верно? Сказать, что logn тесно связан с log8n, означало бы, что logn — это одновременно большая буква O для log8n и большая омега для log8n. Или, говоря простым языком, logn не больше, чем k1 x log8n, и не меньше, чем k2 x log8n.

Я ответил, что logn — это большая омега log8n, потому что он никогда не должен занимать меньше времени. Почему это неправильно?


algorithm computer-science big-o asymptotic-complexity
person Ross Geesman    schedule 15.03.2017    source источник
comment
При использовании больших О и больших Омег постоянные множители и малые аргументы не имеют значения.   -  person Henry    schedule 15.03.2017

Ответы (1)


arrow_upward
2
arrow_downward

Предполагая, что lg обозначает натуральный логарифм, мы имеем log_8(n)=lg(n)/lg(8), поэтому эти две функции различаются только мультипликативным множителем.

Теперь давайте рассмотрим, например, случай Big O из этой таблицы, где f означает lg, а g означает log_8. Если мы установим k=lg(8), то условие в третьем столбце будет выполнено автоматически. Другими словами, условие «| f | ограничено сверху g (с точностью до постоянного множителя)» выполняется, поскольку, грубо говоря, эти две функции фактически одинаковы с точностью до постоянного (мультипликативного) множителя.

То же рассуждение применимо к Big Omega, и поэтому также получается Big Theta (которое вы получаете непосредственно с k1=k2=lg(8) в его определении)

person ewcz    schedule 15.03.2017