Check Levi9 best QA positions to Backbase team!
×Закрыть
👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn

Похожие топики

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Shortest path by Dijkstra, using an unsorted array as priority queue

Это худший случай, в случае полносвязного списка. Если использовать не матрицу, а другую структуру типа многосвязного списка(сеть) то количество операций O(N*Mean(L)) Где N- количество вершин, Mean(L)- среднее количество связей у вершины.

Пруфлинк? Или опять ноотропы подвезли?

Если у вершины обычно всего, к примеру, три связи, то делается такая вот структура
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.

В этот раз у меня разбираться в твоем бреде терпение закончилось

Хотя нет, у меня классический волновой, так как в моей задаче ребра имеют одинаковый вес.

Так что согласен, что для разных весов это не подойдёт.

Мне кажется или Вы слегка неверно понимаете принцип работы алгоритма(хотя быть может я Вас неправильно понял). На каждой итерации вам надо вытолкнуть необработаную вершину с наименьшим расстоянием от исходной вершины графа. Что дает Ваше представление неясно — или Вы предполагаете что после просмотра вершины 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

ru.wikipedia.org/...оритм_поиска_A

AStar опять таки это алгоритм решения несколько другой задачи. Он основывается на евристиках и впринципе не обязан вам выдавать кратчайший путь. На каждом шаге он юзает еврестическую функцию для выбора следующей вершины для просмотра. Поэтому для найденого с помощью А* пути вполне может найтись другой более оптимальный с точки зрения количества шагов

мне всегда было интересно таки big O или таки big Theta

мне всегда было интересно таки big O или таки big Theta
Это вроде как не взаимоисключающие моменты.
UPD. Но вы, я так понял, в курсе ( dou.ua/...ic/7434/#315428 )

Если посмотреть лекции по программированию любого толкового универа, то лекторы говорят Тета или сразу говорят О, но потом исправляются на Тета. Почему? Вся фишка в мат определении. О это верхняя ограниченность, Тета это среднее с приемлимым диапазоном.
для простого кода:

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 и θ это одна и та же буква, они сами не всегда отбивают, что написали

Предлагаю HR почитать и давать алгоритмы на реализацию для синьоров.

Да, отличная шпаргалка чтобы троллить синьйоров на собеседовании.

Не поверите, вопросом а вы точно о big O хотите или о big Theta тролиться половина синиор интервьюверов :)

Чисто интересно, что ТС сделал с данной страницей? Вызубрил? Наклеил на дверь в туалете?

значительно интереснее знать, какой % аудитории в курсе шо воно такэ це О и навищо воно трэба.

Думаю, что очень значительный — часто бывает нужно, чтобы пройти собеседование, а потом верстать CRUD.

Печаль в том, что теперь значительная часть думает, что это просто магический ответ для собеседования и ничего более

Думаю, что очень значительный — часто бывает нужно, чтобы пройти собеседование, а потом верстать CRUD.
гг
поддержал

В CRUD — Тету нужно не знать, а уже жопой чуять, хотя-бы в самых распространенных вариантах, чтобы не вытаскивать так лимон данных на клиента, а потом сортировать пузырьком.

Можно задействовать магию FireBird

Вы про B*-деревья. Если да, то хорошая, правильная магия.

Я про великую силу FireBird для решения любых проблем вообще.

Ну иногда руки чешутся что-то написать, это можно в виде ТЗ себе использовать

Интересно, когда уже тут будет свой собственный хакерньюс, с апвоутами и кармой:).

Подписаться на комментарии