|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 16 Dec 2001 07:29:42
To : Ilia Kantor
Subject : Re: Гоpит отчет по куpсовой. Сpочно! Need help!!!
--------------------------------------------------------------------------------
До меня дошли слухи, что *16.12.01* *0:51:58* пролетало сообщение
от Ilia к *Sergey Politov* про *"Гоpит отчет по куpсовой. Сpочно! Need
help!!!"*. И я решил вмешаться.
IK> У тебя путь с самопеpесечениями будет, я так понимаю?
Да, ты правильно понимаешь.
IK> Если не сложно, тем не менее pасскажи, и желательно попобpобней, как
IK> оно хоть с самопеpесечениями выходит и какова вpеменная оценка/затpаты
IK> памяти основных шагов.
Самопересечения возникают, из-за транзитивного замыкания. Т.е. путь из B в D
может лежать
через A. Теперь о времени. Транзитивное замыкание O(v^3), динамика O(wh), где
w-количество
вершин в оставшемся графе, h - длина последовательности. Оценка O(wh) - очень
грубая, но
всяко меньше O(v^3), кстати если ты так любишь гоняться за алгоритмами с
минимальной
трудоемкостью, то для транзитивного замыкания есть "алгоритм четырех русских" у
него
трудоемкость O(v^3/log(v))
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Metal Invaders. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Гоpит отчет по куpсовой. Сpочно! Need help!!! 