Порядок роста этих выражений?

Question

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

Для следующих выражений, каков порядок роста каждого из них?

п^2 + 2n + 1

п^10 + 9n^9 + 20n^8 + 145N^7

(п + 1)^4

п + лог (п)

(п^3 + 2n)/(п^2 + 0,75)

Я не перечислять их все, потому что я просто хочу, чтобы получить представление о том или понять, как сделать их. Благодаря!

Answer 1

Вот таблица, показывающая сложности Big-O для каждого из ваших выражений. Я думаю, что это то, что вы хотите, когда вы говорите, «порядок роста каждого»:

Expression      Complexity 
------------------------------------------ 
n^2 + 2n + 1     O(n^2) 
n^10 + 9n^9 + 20n^8 + 145n^7 O(n^10) 
(n + 1)^4      O(n^4) 
n + log(n)      O(n) 
(n^3 + 2n)/(n^2 + 0.75)   O(n) 

Одно простое правило, чтобы иметь в виду при расчете сложности Big-O является то, что будет происходить с выражением, как п стремится к бесконечности , Например, рассмотрите свое первое выражение n^2 + 2n + 1. Когда n становится достаточно большим, термин n^2 будет доминировать над поведением выражения.