Как вы представляете базу журнала 100 (N) с большой O, тета, омега

Question

У меня проблемы с поиском, если база лога 100 (n) в O (log (n)), Omega (log (n)) или Theta (log (n)).

Iдумаю, что это в O (log (n)) и только O (log (n)), потому что самое большее у функции будет верхняя асимптотическая граница в log (n), а потому что скорость изменения базы логарифмов 100 n меньше, чем log(n), у него не может быть нижней границы в log (n).

Я новичок в большой О, Омега, Тета, хотя мне любопытно, если мой ответ правильный.

Answer 1

Асимптотические нотации, такие как большие O, большие омега и т. Д., Являются нотациями.

Ω(g(n)) - это набор всех функций в форме f(n), порядок роста которых на больше или равендля значение g(n).

Θ(g(n)) - это набор всех функций в форме f(n), порядок роста которых равен , равен , что g(n).

O(g(n)) - это набор всех функций в форме f(n), порядок роста которых на меньше или равен , чем g(n).

LikeВы указали ниже, поскольку функции отличаются только константой, функция log100(n) является членом всех трех наборов: O(log(n)), Θ(log(n)) и Ω(log(n)).

Я недавно написала статья об асимптотической записи , в которой более подробно об этом говорится.

Answer 2

Big-O - это просто сравнение сложности программ, которое показывает, насколько быстро они растут при увеличении входных данных, а не точное время, затрачиваемое на выполнение действия.

Итак, чтобы сделатьэто просто, в основном используются несколько известных уравнений, и другая база для log фактически не используется в нотациях big-O, и все они просто эквивалентны длинному n.

Что касается вашего комментария, я хотел бы прояснить его:

O, Omega и Theta используются одинаково, но каждый из них имеет различное значение:

• big-O используется для отображения верхней границы роста
• Омега используется для отображения нижней границы роста
• Тета - это точная сложность

ИМХО, в любом из уравнений биг-О вам лучше не использовать более сложные уравнения (вы можете просто придерживаться приведенных выше на графике). Однако вы все равно можете использовать другие более точные уравнения (например, 3 ^ n, n^ 3, ...) но это может бытьиногда вводит в заблуждение!Так что лучше сохранить его как можно более простым.

Относительно log100 (n) также похоже, может быть, вам не нужно точно упоминать это, и использования log (n) будет достаточно?

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