Big-O Algorithm Complexity Cheat Sheet
Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті
Может кому будет полезно
bigocheatsheet.com
Bogdan Shyiak, SE or Dev
Facebook
Twitter
LinkedIn
Alexandr Gavriluk
Shortest path by Dijkstra, using an unsorted array as priority queue
Это худший случай, в случае полносвязного списка. Если использовать не матрицу, а другую структуру типа многосвязного списка(сеть) то количество операций O(N*Mean(L)) Где N- количество вершин, Mean(L)- среднее количество связей у вершины.
reality_hacker
Пруфлинк? Или опять ноотропы подвезли?
Alexandr Gavriluk
Если у вершины обычно всего, к примеру, три связи, то делается такая вот структура
class Vertex
{
SomeVertexValues;
ArrayList Connections;
}
В Connections содержатся линки на вершины к которым они(связи) инцидентны.
В результате обход происходит только массива Connections а не всего массива потенциальной связности текущей вершины.
Конечно если связность задать матрицей, то такого финта не будет.
Ясно, таки ноотропы, в википедии ясно написано что «storing the graph in the form of adjacency lists» а не матрица
По сути записей графа даже в математике довольно много. Например вот матрица смежности ru.wikipedia.org/...трица_смежности
Можно и так. Экономия памяти, но это самый кривой и медленный способ работы с графами.
Мой способ позволяет получить до 50000% ускорения на графах в более 1000 вершин при условии хранения данных в памяти.
Еще раз, это не твой способ, это способ описанный в википедии и называемый adjacency lists, и он не дает описанного тобой выигрыша в вычислительной сложности.
Зато дает в поиске если в
Connectionsбудет прямая ссылка на адрес вершины (класс)
По сути с
adjacency lists. Сложность алгоритма Дейстры это не N^2, а равна количеству связей, которые на реальных задачах редко превышают 1% от N.
Конечно самый худший сферический в вакууме случай даст N^2.
В этот раз у меня разбираться в твоем бреде терпение закончилось
Хотя нет, у меня классический волновой, так как в моей задаче ребра имеют одинаковый вес.
Так что согласен, что для разных весов это не подойдёт.
anonymous
Мне кажется или Вы слегка неверно понимаете принцип работы алгоритма(хотя быть может я Вас неправильно понял). На каждой итерации вам надо вытолкнуть необработаную вершину с наименьшим расстоянием от исходной вершины графа. Что дает Ваше представление неясно — или Вы предполагаете что после просмотра вершины X следующая должна быть инцедента с ней? (так вот это неверно). Ну и даже если заявленная Вами сложность верна — в этом нет ценности. Для разряженных графов, не меняя представления, в качестве очереди с приорететами можно использовать кучу. При этом сложность будет O(nlogn + mlogn), где n — число узлов, а m — соединений в графе
Хотя да, не учел что нужно еще отмечать ребра. Так что ваша сложность более правильная. Но идея просто тупо проверять все вершины на каждом шаге алгоритма могла прийти в голову только джуниору.
Эко Вы Дейкстру унизили. Посмотрите внимательно на сложность выше. В худшем случае, то есть когда граф полный(все имеют связь со всеми) куча дает n * n * logn, в то время как тупой перебор на каждой итерации n * n. Так что все зависит от деталей: разряженный граф — куча, плотный — лучше тупого перебора вроде никто ниче не придумал
На реальных задачах m составляет не более 1% от n. Вот это и нужно учитывать.
Откуда инфа о 1% на реальных задачах? Самая первая, которая мне пришла на ум, поиск минимального пути между двумя перекрестками в городе. Вершины графа — перекрестки, дорога между перекрестками — ребро. В такой задачи можно считать, что степень каждой вершины 4. Тогда (4*n)/2 = m. Это далеко не 1%. Для усложнения можно считать, что граф ориентированный и умножить число ребер на 2. 1% никак не получается.
P.S выше написанное не отменяет того, что существуют задачи с 1%.
На самом деле Вы привели пример сильно разряженного графа, потому что 2 * n ничтожно мало в сравнении с полным вариантом n * n при n стремящигося к бесконечности. Тут таки надо использовать кучу
Я не старался привести пример разреженного графа или спорить о кучах, посыл моего поста касался только фразы
На реальных задачах m составляет не более 1% от nЯ лишь привел пример самой первой задачи, которая приходит мне на ум, где оценка m< n/100 явно ошибочна.
опять прогнал, согласен, хочел сказать 1% от n^2.
тоесть в задаче
(n + m)log(n) где m = 8n имеем
9n*log(n) а это в 11 раз менее n^2 для того же n=1000
Если граф неориентированный то вообще в 20 раз быстрее.
А вообще хорошо что под мою задачу отлично подошел волновой алгоритм, он реально ультра-быстрый, хотя требует одинаковых весов.
Это как бы совсем разные задачи. Все равно, чтобы кто-то занимался задачей с постановкой, учитывающей наличие циклов отрицательной длины, а Вы бы пришли и сказали, что Дейкстра ультра-быстрый, только их не учитывает)
PS: понятно что для одинаковых весов оценку bfs O(n + m) нельзя улучшить даже теоретически без предварительной обработки графа
Собственно и с предварительной не получится, это вообще теоретический минимум.
Хотя если веса между вершинами квантованы(хоть и не равны) и не равны 0, то можно свести к волновому алгоритму через расчет псевдовершин на которые разделить ребра.
Тогда сложность при целом(квантованном) минимальном весе вершины в q и среднем весе вершины вершин в графе Mean(q) будет
(n + m*Mean(q) )
В общем для задачи с перекрестками, если квантовать дальность по 50 метров, а квартал обычно 500 метров, то имеем сложность
для 1000 перекрестков
(1000 + 8000) * 10, тоесть 90k операций.
Это теоретический минимум для алгоритмов без предварительной обработки) Никто не мешает вам имея O(n * n) памяти запрепроцесить граф и для любой произвольной пары вершин высчитать расстояние между ними, все равно как. После этого когда приходит запрос найди мне расстояние между А и Б, вы просто лезете в хештаблицу(матрицу, что удобнее) и отвечаете с амортизированной сложностью O(1)
Обычно я стараюсь так делать, так как за n^2 на алгоритмах меня шеф дрючит, что все довольно медленно.
Посему у меня аллергия на все алгоритмы со сложностью выше nlog(n)
Хотя если граф топологический, то можно свести к волновому и использовать алгоритм AStar, что может в среднем случае дать сложность даже менее N
AStar опять таки это алгоритм решения несколько другой задачи. Он основывается на евристиках и впринципе не обязан вам выдавать кратчайший путь. На каждом шаге он юзает еврестическую функцию для выбора следующей вершины для просмотра. Поэтому для найденого с помощью А* пути вполне может найтись другой более оптимальный с точки зрения количества шагов
Andriy Dobrov
мне всегда было интересно таки big O или таки big Theta
мне всегда было интересно таки big O или таки big ThetaЭто вроде как не взаимоисключающие моменты.
UPD. Но вы, я так понял, в курсе ( dou.ua/...ic/7434/#315428 )
Andriy Dobrov
Если посмотреть лекции по программированию любого толкового универа, то лекторы говорят Тета или сразу говорят О, но потом исправляются на Тета. Почему? Вся фишка в мат определении. О это верхняя ограниченность, Тета это среднее с приемлимым диапазоном.
для простого кода:
for(int i = 0; i < n; i++) {}
О(n) = n, n*n, n**3 ....
Тета (n) = n;
просто для данного примера O(n) = n самое сильное утверждение а O(n) = n*n более слабое.
но с точки зрения мат определения оба варианты ПРАВИЛьНЫЕ. То есть отвечая интервюверу на вопрос какая тут комплексити в О нотации, ответом n! , вы даете правильный ответ. И если за этом нет уточняющего вопроса: а более сильное определение дать можете? То интервьювер только читал ету шпаргалйку а с математикой не особо знаком.
То есть отвечая интервюверу на вопрос какая тут комплексити в О нотации, ответом n! , вы даете правильный ответ. И если за этом нет уточняющего вопроса: а более сильное определение дать можете? То интервьювер только читал ету шпаргалйку а с математикой не особо знаком.Ну если цель проверить интервьюера, то можно и н! отвечать. Если цель показать свои знания, то будете говорить наиболее точную оценку :)
Снова же, в контексте собеседовании, О дает больше размах для маневра, в случае когда у человека нет __жесткого__ КС образования (которое , например, в Украине редкость)
Как-то читал статейку, автор использовал О вместо Омеги (большой). Во многом дело привычки (или выправки)
Полная трехмерная копия Юры Буряка
Если посмотреть лекции по программированию любого толкового универа, то лекторы говорят Тета или сразу говорят ОДа просто когда эти лекторы начинают каракули на доске писать, то у них 0 и θ это одна и та же буква, они сами не всегда отбивают, что написали
idOne Арбузный
Предлагаю HR почитать и давать алгоритмы на реализацию для синьоров.
Да, отличная шпаргалка чтобы троллить синьйоров на собеседовании.
Не поверите, вопросом а вы точно о big O хотите или о big Theta тролиться половина синиор интервьюверов :)
reality_hacker
Чисто интересно, что ТС сделал с данной страницей? Вызубрил? Наклеил на дверь в туалете?
Sergii Voloshyn
Запостил на ДОУ!
значительно интереснее знать, какой % аудитории в курсе шо воно такэ це О и навищо воно трэба.
bsod
Думаю, что очень значительный — часто бывает нужно, чтобы пройти собеседование, а потом верстать CRUD.
Oleg Bogdanov
Печаль в том, что теперь значительная часть думает, что это просто магический ответ для собеседования и ничего более
Думаю, что очень значительный — часто бывает нужно, чтобы пройти собеседование, а потом верстать CRUD.гг
поддержал
В CRUD — Тету нужно не знать, а уже жопой чуять, хотя-бы в самых распространенных вариантах, чтобы не вытаскивать так лимон данных на клиента, а потом сортировать пузырьком.
Andrii Serhiienko
Можно задействовать магию FireBird
Вы про B*-деревья. Если да, то хорошая, правильная магия.
Я про великую силу FireBird для решения любых проблем вообще.
idOne Арбузный
Ну иногда руки чешутся что-то написать, это можно в виде ТЗ себе использовать
осокор тауер
Интересно, когда уже тут будет свой собственный хакерньюс, с апвоутами и кармой:).
45 коментарів
Додати коментар Підписатись на коментаріВідписатись від коментарів