Помощь с большой нотацией

Question

У меня были некоторые проблемы, пытаясь понять концепцию больших О-нотаций. Итак, по определению большой O выглядит следующим образом: T(n) ∈ O(G(n)) if T(n) <= G(n) * C.

Поскольку константа "C" может быть любым целым числом> 0, разве этот следующий пример также не будет верным?

Пример:

n log n ∈ O(log n)
n log n <= log n * c

Где C равно значению n.

Я знаю, что ответ таков: n log n ∉ O(log n), но я не понимаю, как, поскольку C может быть любой константой.

Заранее спасибо за помощь: D

Answer 1

с - это просто константа . Это означает, что вы не можете сказать «пусть c будет значением n», потому что вы должны сначала выбрать несколько c, а затем разрешить сравнение для всех n.

Другими словами, для того, чтобы некоторый T (n) был O (G (n)), должна существовать нет константа c, так что G (n) * c больше, чем T ( n) для всех n.

Таким образом, n log n не является O (log n), потому что, независимо от того, какую константу вы выберете, n> c приведет к тому, что n log n будет больше, чем c log n.

Answer 2

Идея состоит в том, что неравенство выполняется для любых n и a fixed c.таким образом, хотя вы можете найти определенный c такой, что n log n n), вы можете легко найти другой n ', для которого он не выполняется (а именно n'> c).

Answer 3

Позвольте мне повторить ваши слова.

c может быть любой постоянной .

Это означает, что c не может зависеть от n.

Answer 4

Прежде всего, если n = C, то C не является константой. И в большинстве реальных алгоритмов C мало, поэтому часть big-O обычно доминирует для типичных значений n.

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

Если вы знаете, что n * всегда маленькое, то сложность big-O не так важна, скорее вы должны сосредоточиться на времени настенных часов, требуемом алгоритмом. Кроме того, если вы выбираете между двумя алгоритмами, которые имеют одинаковую сложность big-O (например, O (n log n)), довольно часто один лучше, чем другой (например, быстрая сортировка по случайному повороту обычно превосходит двоичную сортировку кучи).

Answer 5

Всякий раз, когда я застреваю на большом, я нахожу полезным думать об этом как о соревновании: Я выбираю функцию big-oh (так, в вашем случае, logn) и константу (c). Важно то, что я должен выбрать реальную стоимость. Я обычно выбираю тысячу, просто потому что. Тогда я должен позволить своему заклятому врагу выбрать любой n, который он выберет . Обычно он выбирает миллиард.

Тогда я сделаю сравнение.

Чтобы завершить пример, 10 ^ 9 * (log (10 ^ 9)) теперь явно намного больше, чем 1000log (10 ^ 9). Таким образом, я знаю, что биг-о не будет работать.

Answer 6

Значение n зависит от набора входных данных, значение C является фиксированным.

Так что да, если n = 16 и C = 256, это выглядит как n ^ 2 * lg (n) для небольшого набора ввода.Теперь увеличьте входной набор до 100 000 000;значение C остается равным 256, теперь у вас есть 256 * lg (100 000 000)

Answer 7

в выражении n log n, вы не можете сравнивать внешние n с C, как вы делаете.Это все равно что взять алгебраическое выражение x (x + 1) и заменить одно из x на константу.

В n log n n является переменной.В большом выражении O C является константой.

Answer 8

В определении вы должны определить C только самими T и G.Это то, что означает константа C.Поэтому C не должен зависеть от их ввода.Таким образом, вы не можете рассмотреть C = N

Answer 9

Я думаю, что эта ссылка может прояснить для вас вещи.

http://mohalgorithmsorbit.blogspot.com/2013/12/complexity-theory-approaching.html