Я задаю этот вопрос, потому что я запутался в одном аспекте, касающемся обозначения больших О.
Я использую книгу Фрэнка Каррано « Структуры данных и абстракции с Java ». В главе «Эффективность алгоритмов» он показывает следующий алгоритм:
int sum = 0, i = 1, j = 1
for (i = 1 to n) {
for (j = 1 to i)
sum = sum + 1
}
Первоначально он описывает этот алгоритм как имеющий скорость роста (n 2 + n) / 2 . Который смотрит на это кажется интуитивным.
Однако затем утверждается, что (n 2 + n) / 2 ведет себя как n 2, когда n большое. В том же абзаце он утверждает (п 2 + п) / 2 также ведет себя так же, как п 2 / 2 . Он использует это, чтобы классифицировать вышеупомянутый алгоритм как O (n 2 ) .
Я получаю , что (п 2 + п) / 2 аналогично п 2 / 2 , так как в процентном отношении, п имеет небольшое значение. Я не понимаю, почему (n 2 + n) / 2 и n 2 похожи, когда n большое.
Например, если n = 1 000 000 :
(n^2 + n) / 2 = 500000500000 (5.000005e+11)
(n^2) / 2 = 500000000000 (5e+11)
(n^2) = 1000000000000 (1e+12)
Этот последний не похож на всех. На самом деле, совершенно очевидно, что он вдвое больше среднего. Так как же Фрэнк Каррано сказать, что они похожи? Кроме того, как алгоритм классифицируется как O (n 2 ) . Глядя на этот внутренний цикл, я бы сказал, что это n 2 + n / 2
источник
n
роста функции 'n ^ 2` и ваша функция ведут себя одинаково, что приводит к постоянной неуверенности в скорости их роста. Если у вас сложное выражение, функция, которая растет быстрее, доминирует.Ответы:
При вычислении сложности алгоритма Big-O показанная вещь является фактором, который дает наибольший вклад в увеличение времени выполнения, если число элементов, над которыми вы запускаете алгоритм, увеличивается.
Если у вас есть сложный алгоритм,
(n^2 + n)/2
и вы удваиваете количество элементов, то константа2
не влияет на увеличение времени выполнения, терминn
вызывает удвоение времени выполнения, а терминn^2
вызывает четырехкратное увеличение времени выполнения. время.Поскольку
n^2
термин имеет наибольший вклад, сложность Big-O равнаO(n^2)
.источник
O(n * log n) = O(n)
, что это не так.O(n * log n) = O(n)
. Я думаю, что это дает хорошее объяснение обоснования определения.Определение таково, что
если существует некоторая постоянная C> 0 такая, что для всех n, больших n_0, имеем
Это очевидно верно для f (n) = n ^ 2 и g (n) = 1/2 n ^ 2, где константа C должна быть 2. Также легко видеть, что это верно для f (n) = n ^ 2 и g (n) = 1/2 (n ^ 2 + n).
источник
g
ненулевая, это на самом деле не нужно, так как вы всегда можете увеличить константу C, чтобы сделать утверждение истинным для конечного числа первых значений n_0.Говоря о сложности, вас интересуют только изменения временного фактора в зависимости от количества элементов (
n
).Таким образом, вы можете удалить любой постоянный фактор (как
2
здесь).Это оставляет вас с
O(n^2 + n)
.Теперь, для достаточно большого
n
продукта, т. Е.n * n
Будет значительно больше, чем простоn
, что является причиной, по которой вам также разрешено пропустить эту часть, что оставляет вас действительно с окончательной сложностьюO(n^2)
.Это правда, для небольших чисел будет существенное различие, но оно становится тем незначительнее, чем больше вы
n
становитесь.источник
Дело не в том, что «(n² + n) / 2 ведет себя как n², когда n большое», а в том, что (n² + n) / 2 растет как n² при увеличении n .
Например, при увеличении n от 1000 до 1000000
Точно так же, как n увеличивается от 1 000 000 до 1 000 000 000
Они растут так же, как и в Big O Notation.
Если вы нанесете (n² + n) / 2 и n² / 2 на Wolfram Alpha , они настолько похожи, что их трудно различить по n = 100. Если вы нанесете все три на Wolfram Alpha , вы увидите две линии, разделенные постоянным множителем 2.
источник
Похоже, вам нужно немного больше проработать нотацию большого О. Насколько удобно это обозначение, оно вводит в заблуждение из-за использования знака равенства, который здесь не используется для обозначения равенства функций.
Как вы знаете, это обозначение выражает асимптотическое сравнение функций, и запись f = O (g) означает, что f (n) растет не более, чем g (n), так как n уходит в бесконечность. Простой способ перевести это - сказать, что функция f / g ограничена. Но, конечно, мы должны заботиться о тех местах , где г равно нулю, и мы получим более надежное определение, которое вы можете прочитать почти везде .
Эти обозначения оказываются очень удобными для вычислений - вот почему они так широко распространены - но с ними следует обращаться осторожно, поскольку знак равенства, который мы видим там, не обозначает равенство функций . Это очень похоже на то, что 2 = 5 мод 3 не означает, что 2 = 5, и если вы увлекаетесь алгеброй, вы можете реально понимать обозначение большой О как равенство по модулю чего-то.
Теперь, чтобы вернуться к вашему конкретному вопросу, совершенно бесполезно вычислять несколько числовых значений и сравнивать их: каким бы большим ни был миллион, он не учитывает асимптотическое поведение. Было бы более полезно изобразить соотношение функций f (n) = n (n-1) / 2 и g (n) = n² - но в этом частном случае мы легко видим, что f (n) / g (n) меньше 1/2, если n> 0, что означает, что f = O (g) .
Чтобы улучшить ваше понимание обозначений, вы должны
Работайте с четким определением, а не с нечетким впечатлением, основанным на похожих вещах - как вы только что это испытали, такое нечеткое впечатление не сработает.
Потратьте некоторое время, чтобы детально проработать примеры. Если вы отработаете всего пять примеров за неделю, этого будет достаточно, чтобы повысить вашу уверенность. Это усилие, которое определенно стоит.
Замечание об алгебре. Если A - алгебра всех функций Ν → Ν, а C - подалгебра ограниченных функций, то для данной функции f множество функций, принадлежащих O (f), является C -подмодулем A , и правила вычисления на большом Обозначения O просто описывают, как A работает с этими подмодулями. Таким образом, равенство, которое мы видим, является равенством C -подмодулей A , это просто еще один вид модуля.
источник
Я думаю, вы неправильно понимаете, что означает большая буква О.
Когда вы видите O (N ^ 2), это в основном означает: когда проблема становится в 10 раз больше, время ее решения будет: 10 ^ 2 = в 100 раз больше.
Давайте пробьём 1000 и 10000 в вашем уравнении: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000
50005000/500500 = 99,91
Таким образом, в то время как N увеличился в 10 раз, решения выросли в 100 раз. Следовательно, он ведет себя: O (N ^ 2)
источник
1000000000000.00 что?
Хотя сложность дает нам возможность предсказать реальную стоимость (секунды или байты в зависимости от того, говорим ли мы о временной или пространственной сложности), она не дает нам количество секунд или какую-либо другую конкретную единицу.
Это дает нам степень пропорции.
Если алгоритм должен что-то делать n² раз, то для некоторого значения c, то есть того, сколько времени занимает каждая итерация, потребуется n² × c.
Если алгоритм должен что-то делать n² ÷ 2 раза, то для некоторого значения c, которое в два раза дольше, чем для каждой итерации, потребуется n² × c.
В любом случае, затраченное время все еще пропорционально n².
Теперь эти постоянные факторы нельзя игнорировать; действительно, у вас может быть случай, когда алгоритм со сложностью O (n²) работает лучше, чем алгоритм со сложностью O (n), потому что если мы работаем над небольшим количеством элементов, то влияние сопутствующих факторов будет больше и может преодолеть другие проблемы , (Действительно, даже O (n!) Совпадает с O (1) для достаточно низких значений n).
Но это не то, о чем говорит нам сложность.
На практике есть несколько способов улучшить производительность алгоритма:
Или, если посмотреть по-другому, у нас есть
f(n)×c
несколько секунд, и вы можете улучшить производительность, уменьшивc
, уменьшивn
или уменьшивf
доходность для данногоn
.Первое, что мы можем сделать, используя некоторые микроопты внутри цикла, или используя лучшее оборудование. Это всегда даст улучшение.
Второе, что мы можем сделать, возможно, выявив случай, когда мы можем закорачивать алгоритм до того, как все будет исследовано, или отфильтровать некоторые данные, которые не будут иметь существенного значения. Это не даст улучшения, если стоимость выполнения этого перевесит выигрыш, но обычно это будет большее улучшение, чем в первом случае, особенно с большим n.
Третье, что мы можем сделать, используя совершенно другой алгоритм. Классическим примером будет замена пузырьковой сортировки быстрой сортировкой. При небольшом количестве элементов мы могли бы ухудшить ситуацию (если c₁ больше, чем c₀), но обычно это дает наибольший выигрыш, особенно при очень большом n.
При практическом использовании меры сложности позволяют нам рассуждать о различиях между алгоритмами именно потому, что они игнорируют вопрос о том, как поможет уменьшение n или c, чтобы сосредоточиться на рассмотрении
f()
источник
n
достаточно низкое, значение Big-O не имеет значения».Постоянный фактор
Смысл больших обозначений O заключается в том, что вы можете выбрать произвольно большой постоянный множитель, чтобы O (function (n)) всегда было больше, чем C * function (n). Если алгоритм A в миллиард раз медленнее, чем алгоритм B, то они имеют одинаковую сложность O, если эта разница не увеличивается, когда n растет сколь угодно большим.
Давайте предположим постоянный коэффициент 1000000, чтобы проиллюстрировать концепцию - это в миллион раз больше, чем необходимо, но это показывает, что они считаются неактуальными.
(n ^ 2 + n) / 2 «вписывается в» O (n ^ 2), потому что для любого n, независимо от его размера, (n ^ 2 + n) / 2 <1000000 * n ^ 2.
(n ^ 2 + n) / 2 «не подходит» меньшему набору, например, O (n), потому что для некоторых значений (n ^ 2 + n) / 2> 1000000 * n.
Постоянные факторы могут быть сколь угодно большими - алгоритм со временем выполнения n лет имеет сложность O (n), которая "лучше", чем алгоритм со временем работы n * log (n) микросекунд.
источник
Big-O - все о том, насколько сложен алгоритм. Если у вас есть два алгоритма, и одному требуется
n^2*k
несколько секунд для запуска, а другому -n^2*j
секунды, то вы можете поспорить о том, какой из них лучше, и вы можете сделать некоторые интересные оптимизации, чтобы попытаться повлиятьk
илиj
, но оба эти алгоритмы очень медленные по сравнению с алгоритмом, который требуетсяn*m
для запуска. Неважно, насколько малы вы делаете константы,k
илиj
, если вход достаточно большой,n*m
алгоритм всегда выиграет, даже еслиm
он достаточно велик.Итак, мы называем первые два алгоритма
O(n^2)
и называем второйO(n)
. Он красиво делит мир на классы алгоритмов. Это то, что Big-O это все. Это похоже на разделение транспортных средств на легковые и грузовые автомобили, автобусы и т. Д. Между автомобилями много различий, и вы можете провести целый день, споря о том, лучше ли Prius, чем Chevy Volt, но в конце дня, если вы нужно собрать 12 человек в один, тогда это довольно бессмысленный аргумент. :)источник