У меня были некоторые проблемы, пытаясь понять концепцию большой нотации O. Итак, по определению большой 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
c - это просто константа. Это означает, что вы не можете сказать «пусть c будет значением n», потому что вы должны сначала выбрать некоторое c, а затем разрешить сравнение для всех n.
Другими словами, чтобы некоторое T(n) было равно O(G(n)), не должно существовать никакой константы c такой, что G(n)*c больше, чем T(n) для всех н.
Таким образом, n log n не равно O(log n), потому что независимо от того, какую константу вы выберете, n > c приведет к тому, что n log n будет больше, чем c log n.
Позвольте мне повторить ваши слова.
c может быть любой константой.
Это означает, что c не может зависеть от n.
идея состоит в том, что неравенство выполняется для любого n и фиксированного c. поэтому, хотя вы можете найти определенное c такое, что n log n ‹ c log n (а именно, любое c>n), вы можете легко найти другое n', для которого это не выполняется (а именно n'>c).
Прежде всего, если n=C, то C не является константой. И в большинстве реальных алгоритмов C мало, поэтому большая часть O обычно доминирует для типичных значений n.
Но сложность большого O связана с эффективностью алгоритма для больших n, особенно когда n приближается к бесконечности. Другими словами, он говорит вам о масштабируемости алгоритма: насколько хорошо данный алгоритм справляется с очень большой или удвоенной рабочей нагрузкой.
Если вы знаете, что n всегда мало, то сложность большого O не так важна, скорее вам следует сосредоточиться на времени настенных часов, требуемом алгоритмом. Кроме того, если вы выбираете между двумя алгоритмами, которые имеют одинаковую сложность большого O (например, O (n log n)), довольно часто один из них лучше, чем другой (например, быстрая сортировка со случайным сводом обычно превосходит сортировку двоичной кучи).
k выше). Это не может быть экзистенциальная переменная (X выше) или экзистенциальная константа (j), потому что они не существуют для реальных алгоритмов. Но вы говорите, что если n=C, то C не константа. Поэтому где-то в ваших первых двух предложениях вы путаетесь.
- person Borealid; 12.04.2011
В определении вы должны определить C только по самим T и G. Вот что означает константа C. Поэтому C не должен зависеть от их ввода. Так что нельзя считать C = n
в выражении n log n нельзя сравнивать внешний n с C, как вы это делаете. Это все равно, что взять алгебраическое выражение x(x+1) и заменить один из x константой.
В n log n n является переменной. В большом выражении O C является константой.
Значение n зависит от входного набора, значение C фиксировано.
Так что да, если n = 16 и C = 256, это выглядит как n^2 * lg(n) для небольшого набора входных данных. Теперь увеличьте входной набор до 100 000 000; значение C остается равным 256, теперь у вас есть 256 * lg (100 000 000)
Всякий раз, когда я застреваю на большом-о, я считаю полезным думать об этом как о соревновании: я выбираю большую-о-функцию (то есть, в вашем случае, logn) и константу (c). Важно то, что я должен выбрать реальное значение. Я обычно беру тысячу, просто так. Затем я должен позволить моему заклятому врагу выбрать любое n, которое он выберет. Обычно он выбирает миллиард.
Потом делаю сравнение.
Чтобы закончить пример, 10 ^ 9 * (log (10 ^ 9)) теперь явно намного больше, чем 1000 log (10 ^ 9). Таким образом, я знаю, что большое-о не сработает.
