Справка с большой нотацией O

c - это просто константа. Это означает, что вы не можете сказать "пусть 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.

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

c может быть любой константой .

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

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

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

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

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

Тогда я провожу сравнение.

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

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

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

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

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

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

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