Что такое большой O для сложности O (sqrt (n) * log (sqrt (n))) + O (n)

Question

Какая будет обозначение Big O для вышеуказанной сложности?

ли О (п)

Answer 1

Да. Главное то, что квадратный корень внутри журнала не имеет никакого значения:

O(sqrt(n) log(sqrt(n))) = O(sqrt(n) 1/2 log(n)) = O(sqrt(n) log(n)). 

с этой стороны, мы замечаем

O(n) = O(sqrt(n)sqrt(n)) > O(sqrt(n)log(n)). 

Это происходит потому, что в любом случае

O(sqrt(n)) > O(log(n)). 

Почему? Мы можем взять журнал с обеих сторон, чтобы проверить, и снова квадратный корень появляется в журнале:

O(log(sqrt(n)) = O(1/2 log(n)) = O(log(n)) > O(log log(n)) 

Таким образом, мы можем, наконец, заключить общий результат O (п).

Answer 2

O (п) заглушает O (SQRT (п)) и O (журнал (SQRT (п))

Answer 3

O (SQRT (п) * журнал (SQRT (п))) + О (п) < = O (SQRT (п) * SQRT (п)) + О (п)

O (SQRT (п) * SQRT (п)) + О (п) = О (п) + О (п)

О (п) + О (п) = О (п)