Большая-O сложность c^n + n* (logn) ^2 + (10*n) ^c
Я должен получить Большую-O сложность этого выражения:
c^n + n* (журнал (n)) ^2 + (10*n) ^c
где c является константой, и n является переменной.
Я вполне уверен, я понимаю, как получить Большую-O сложность каждого термина индивидуально, я просто не знаю, как Большая-O сложность изменяется, когда условия объединены как это.
Идеи?
Любая справка была бы большой, спасибо.
3 ответа
Нотация O() учитывает самый высокий член; подумайте, какой из них будет доминировать для очень и очень больших значений n.
В вашем случае наивысшим членом является c^n, на самом деле; остальные, по сути, многочленные. Таким образом, это экспоненциальная сложность.
В типичном использовании формальное определение O обозначения не используются напрямую; скорее, обозначение O для функции f (x) выводится с помощью следующих правил упрощения:
- Если f (x) является суммой нескольких членов, то сохраняется одно с наибольшей скоростью роста, а все остальные опускаются.
- Если f (x) является произведением нескольких факторов, любые константы (члены в произведении, не зависящие от x) опускаются.
Ответ зависит от | c |
Если | c | <= 1 это O (n * (log (n)) ^ 2)
IF | c | > 1 это O (c ^ n)