Большой О или Большой тета?

Предположим, у нас есть функция f(n)=log n и другая функция g(n)=log n^2. Вопрос в том, f(n)=O(g(n)) или f(n)=big_Theta(g(n)). Поскольку log n ^ 2 = 2 log n, то другой способ задать мой вопрос: можем ли мы использовать дробь как константу k? Для параметра big_Theta у меня было бы что-то вроде k1=1/4 для нижней границы и k2=1 для верхней границы. Это нормально?

Очевидно, что k не может быть нулевым или отрицательным, но я не уверен насчет дроби и не нашел четкого ответа в Интернете или в книгах, которые просматривал.

Заранее спасибо за помощь.


algorithm big-o complexity-theory big-theta asymptotic-complexity
person J. Mandy    schedule 22.10.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Оба f (n) = Θ (g (n)) и f (n) = Θ (g (n)). Также обратите внимание, что в то же время верно, что f(n)=O(g(n)). Интуитивно big-oh означает, что f ограничено сверху величиной g(n) (т. е. растет не быстрее, чем g). С другой стороны, большая тета означает, что f ограничено g как сверху, так и снизу (т. е. растет точно так же быстро, как g). Обратите внимание, что последние два предложения не являются абсолютно точными, чтобы их было легче понять и сосредоточиться на интуитивном значении этого, а не на его теории.

person Ivaylo Strandjev    schedule 22.10.2015
comment
Спасибо за ваш ответ. Я просто хотел быть уверенным в этой технической детали (k = дробь), и вы, кажется, подтверждаете мою интуицию. - person J. Mandy; 23.10.2015
comment
@ J.Mandy да, любое действительное число можно использовать как k. - person Ivaylo Strandjev; 23.10.2015