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

Question

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

п = # элементов данных манипулируют

1) N 3 + N 2 журнала^^ (основание 2) п + п 3 журнала^(основание 2) п

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), поэтому любой логарифм отличается от другого константой.

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

Answer 2

Вам не нужно «вычислить сложность для базового номера», вы можете просто сравнить темпы роста, что и в других терминах (см это graph of logarithm growth rates, чтобы дать вам идею)

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

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

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

Answer 3

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

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

1) п 3 журнала^(п)

2) п^3