Comments 21
> Обозначение Big O нотация (или просто Big O) — это способ оценки относительной производительности структуры данных или алгоритма, обычно по двум осям: времени и пространству.
Это о сложности, а о времени. Да, некоторые закономерности прослеживаются.
Но вот контр пример, возьмем такую задачу: нужно нам обойти ровно миллион ссылок. Как не крути это долго. Раз мы знаем точное количество ссылок, значит время константное O(1), алгоритм выполнится за фиксированное количество шагов. Это не очень полезно, с точки зрения оценки алгоритма, но математика она такая :)
Мне нравится, как вопрос сложности разобран в книге Cracking the code interview.
O(1) is very fast, for sufficiently low values of 1.
это очень полезно с точки зрения оценки алгоритма. Смысл в том чтобы показать что программа будет всегда исполнятся одно и тоже время (при идентичной среде) вне зависимости от входных параметров. И если вчера оно заняло 10 часов, это значит что и сегодня оно займёт 10 часов, вы можете это утверждать и оперировать этим описываю остальную бизнес логику.
hashA[a] = true
Dictionary для этой здачи совсем не подходит по логике. Есть более простая структура данных, которые просто идеально подходит к данной задаче - set https://www.programiz.com/swift-programming/sets. Под капотом обычно тоже самое что в словаре, только без значений.
Если допустимо изменить порядок элементов во входных массивах, то можно их отсортировать и найти общие элементы за один проход без дополнительной памяти.
С учётом времени на сортировку будет время O(n*log(n)). Немного похуже, чем с хеш-таблицей, но гораздо быстрее, чем решение "в лоб".
Спасибо за пример. В моём случае хотел показать вариант обмена на память, чтобы подходил по смыслу к заголовку.
А сортировка за n*log(n) тоже без дополнительной памяти?
Сортировка это слишком абстрактно. Quick sort да, merge sort нет.
Ну вот я и спрашиваю, в контексте
...можно их отсортировать и найти общие элементы за один проход без дополнительной памяти...
у меня есть подозрение, что "чудес не бывает", особенно, если рассматривать общие случаи, а не какое-то подмножество входных данных. Это не отменяет возможности оптимизаций под конкретные задачи, естественно.
Для Питона, есть небольшая табличка со сложностью операций над основными структурами данных. https://wiki.python.org/moin/TimeComplexity
Что-то такое должно быть и для остальных языков.
O(n) описывает характер изменения затрачиваемого времени, при этом конкретное время зависит от константы c, т.е. полностью O(cn). с в нотации не указывают, но про её влияние стоит помнить. O(n) - это не одна линия на графике, а бесконечное множество линий. При определённых условиях O(n) может быть медленнее, чем O(n^2).
Очень интересные замечания, не могли бы вы дополнить их примерами или ссылками где можно почитать про это?
Почитать - думаю Кнут подойдёт. У него же есть и про другие оценки, а не только О.
По примерам - пример чего интересует?
Например, насколько медленым может быть алгоритм с асимптотикой O(n)? Можно логически вывести, что сколь угодно медленым)
Нет такой оценки, как O(2n), т.к. 2 - это константа с, которую не указывают. Если алгоритм состоит из нескольких частей, каждая из которых имеет линейную оценку, то суммарная оценка также будет линейной. Т.е. O(n) + O(n) +...+ O(n) = O(n). Из этого можно сделать вывод, что алгоритм может быть очень медленым, при этом оставаясь линейным. В то же время алгоритм с оценкой O(n^2) может быть довольно быстрым, при этом сохраняя квадратичную зависимость времени исполнения от количества входных данных. На практике на больших данных результаты в основном будут соответствовать ожиданиями.
Дональд кнут значит, интересно, спасибо за наводку!)
Как же так? O(cn) - это просто с последовательных циклов, которые можно легко свести к одному циклу, приведя тем самым алгоритм O(cn) к O(n). Именно поэтому константу всегда и упускают в такой нотации. Так что любой самый медленный O(cn) всегда можно сделать быстрее, чем O(n^2). Или есть какие-то случаи, когда нельзя? Можно примеры таких случаев?
O(cn) - константа определяет, сколько времени уходит на обработку одного элемента. Точно определить её очень сложно, поэтому из оценки О(n), мы не можем высчитать точное время, несмотря на то, что знаем n.
Почти все эффективные алгоритмы сортировки имеют оценку O(nlogn). За какое время они отсортируют массив из 1000 элементов? А за какое время такой массив отсортирует "пузырёк"?
Мне казалось, что под константой с подразумевают все же количество повторений последовательных циклов, а не время выполнения одного прогона цикла.
Но даже если и смотреть на с под таким углом, как говорите Вы, то получим мы следующее. Константы с1 и с2 будут лишь определять точку пересечения графиков друг с другом. Как экспонента и логарифм. Всем понятно, что экспонента на больших значениях более медленный алгоритм, чем логарифм. Но на значениях до 1, у них прямо противоположный эффект.
То же самое и Вы пытаетесь показать, только сдвинув точку пересечения от 1 гораздо дальше вправо и вверх. Но мне кажется, что это должны быть очень большие значения с соответствующие каким-то жутко неэффективны алгоритмам. При этом значениям н будут все еще ничтожно малы.
Для упомянутых вами алгоритмов, кмк, эти значения не такие ужасные. Да и инвертирование картинки получится лишь на малых значениях н до точки пересечения графиков. А дальше мы все равно будем получать "теоретический" неперевернутый результат. А смысл искать оптимальный алгоритм на малых значениях n? Там вообще не важно, оптимален алгоритм или нет. Быстр он или нет. А вот как можно исковеркать алгоритм так, чтобы точка пересечения графиков ушла так далеко вправо, чтобы даже на больших значениях n упомянутая вами картина была верна, я даже думать не хочу. Это что-то из области такого страшного говнокода, что надеюсь, никогда я с этим не повстречаюсь.
И все же ближе к практике. Упомянутые Вами алгоритмы на n=1000 дают инвертированную картину? Вы проводили исследования? Можно где-то почитать?
Вы всё правильно понимаете. O большое описывает характер графика, но не его положение на графике t(n), поэтому однозначно говорить про "быстрее/медленнее" нельзя. Случаи, когда реальное время не будет соответствовать ожиданиям, основанным на оценке O, возможны и на практике встречаются, но надеюсь, что это больше исключение.
1
Big O нотация в Swift