Как определить, является ли что-то частью большой функции Oh?

Question

Я работаю над этой домашней работой около 4 часов, и мне удалось выяснить несколько вопросов по этому вопросу, но я до сих пор не знаю, о чем это говорит:

Какой из следующее верно, а что ложно и почему?

(а) √n^5 ∈ O (N^2)

(б) √n войти √n ∈ O (п)

(с) журнал (п^3) ∈ O (п § п)

(г) 2/п + 4/п^2 ∈ Θ (1/п)

(е) (log_2 (п)) ^. 5 ∈ Θ (журнал (п))

(f) min (700, n^2) ∈ Θ (1)

Я понимаю, что я должен взять f (n)/g (n) и поставить его в пределе при n-> бесконечности и решить .. но это дает мне 0 для каждого из них, и Я знаю, что это неправильно.

Как это сделать?

Большое спасибо.

Answer 1

Итак, вы можете думать об этом двумя способами. Одним из них является то, как вы представляли, ф (п)/г (п) при п> бесконечности, значение приближается к 0. Или, как я думаю, что проще:

There is some pair of constants A and B such that A * g(n) + B > f(n) for all n. 

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

Обычно вы игнорируете значение B и просто убедитесь, что A * g (n) растет быстрее, чем f (n). Б - просто формальность.