 |
|
|
 
|
|
Нужен алгоритм обхода ненаправленного графа 
| KQT |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 17.10.2007 Репутация: нет Всего: нет |
Доброго вечера!..
Существует ли алгоритм обхода ненаправленного графа: линейный по количеству вершин и константный по памяти? Критическим является второе требование, т. е. буду рад и более медленному алгоритму, лишь бы он не требовал дополнительной памяти. Существует ли такой алгоритм для деревьев? |
|||
|
||||
Загрузка ...
| esperanto |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
Константный по памяти не существует. Есть за лог(п) памяти и больше
--------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
| KQT |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 14 Регистрация: 17.10.2007 Репутация: нет Всего: нет |
Как называется?
Доказано, что лучше нельзя? |
|||
|
||||
| esperanto |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 31.5.2003 Репутация: 2 Всего: 4 |
То что нельзя за константное количество памяти достаточно очевидно. Ведь надо или считать сколько шагов сделал алгоритм или помечать вершины которые алгоритм уже поситил. Первый подход требует переменную счетчик второй линейное количество памяти. --------------------
B.Sc ->M.Sc.->Microsoft SDE-> (Ph.D. student + Intel SDE + psyсhology B.A) - > Skype SDET |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0504 ] [ Использовано запросов: 20 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |