Мне хотелось бы узнать, кем и когда был впервые придуман этот алгоритм. Я нашел описания здесь и здесь, но ссылок на источник нет. Публиковался ли он где-нибудь, или это метод, придуманный исключительно спортивными программистами?

задан 2 Дек '11 4:03

1

Небольшое гугление показывает, что этим интересовался Tarjan (R.E. Tarjan. Applications of path compression on balanced trees 1979) и в 84 году он научился делать это за O(1) (D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors. 1984). А вообще у меня сложилось подозрение, что алгоритм поиска LCA есть в Искусстве программирования Кнута -- поищи.

(2 Дек '11 12:38) Ignat
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×76
×9

задан
2 Дек '11 4:03

показан
1136 раз

обновлен
2 Дек '11 12:38

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru