Большая сложность для логарифмических алгоритмов

Question

Еще несколько проблем, с которыми я столкнулся при расчете сложности Big-oh.Есть 2 проблемы, которые я не могу решить из-за операций базы журналов.Вот две проблемы:

n = количество элементов данных, которыми манипулируют

1) n ^ 3 + n ^ 2 log (база 2) n + n ^ 3 log (база 2)n

2) 2n ^ 3 + 1000n ^ 2 + log (база 4) n + 300000n

Я в замешательстве, когда журналы имеют базовый номер.Как вы рассчитываете сложность для них?Кто-нибудь хочет объяснить, как вы получаете сложность с небольшой детализацией, если это возможно?

Answer 1

Основание логарифма не имеет значения. Вы можете просто игнорировать это. Поэтому:

1) Это O(n^3 log n), потому что это термин, который растет быстрее всего.

2) Это O(n^3) по той же причине.

База не имеет значения, потому что log base a (x) = log base b (x) / log base b (a), поэтому любой логарифм отличается от другого на постоянную.

Предлагаю вам больше узнать о свойствах логарифма здесь .

Answer 2

При вычислении асимптотической сложности предполагается, что n очень велико и, таким образом, константы можно игнорировать. Если у вас есть сумма, учитывайте только самый большой срок.

В ваших примерах это приводит к:

1) n ^ 3 log (n)

2) n ^ 3

Answer 3

Вам не нужно «вычислять сложность для базового числа», вы можете просто сравнить его темп роста с другими терминами (см. Этот график скорости роста логарифма , чтобы получитьидея)

Обратите внимание, что для решения этих проблем не нужно обращать внимание на базу журналов.

O(x + y + z) === O(max(x,y,z))

Итак, решите, какой из суммированных терминов является наибольшим иВы можете решить свои проблемы.