Big-O сложность c ^ ​​n + n * (logn) ^ 2 + (10 * n) ^ c

Question

Мне нужно вывести сложность Big-O этого выражения:

c ^ n + n * (log (n)) ^ 2 + (10 * n) ^ c

где c - постоянная, а n - переменная.
Я почти уверен, что понимаю, как получить сложность Big-O для каждого термина в отдельности, я просто не знаю, как изменяется сложность Big-O, когда термины объединяются следующим образом. Идеи?

Любая помощь будет отличной, спасибо.

Answer 1

Ответ зависит от | c |

Если | c | <= 1 это O (n * (log (n)) ^ 2) </p>

IF | c | > 1 это O (c ^ n)

Answer 2

Обозначение O () рассматривает самый высокий член; подумайте о том, какой из них будет доминировать при очень и очень больших значениях n.

В вашем случае, самый высокий срок - c^n, на самом деле; остальные по существу полиномиальны. Итак, это экспоненциальная сложность.

Answer 3

Википедия - твой друг :

При типичном использовании формальное определение нотации O не используется напрямую; скорее, обозначение O для функции f (x) получено по следующим правилам упрощения:

• Если f (x) является суммой нескольких слагаемых, то значение с наибольшим темпом роста сохраняется, а все остальные опускаются.
• Если f (x) является произведением нескольких факторов, любые константы (члены в произведении, не зависящие от x), опускаются.