Про великое в алгоритмах

[griffon]

Удалось сегодня задать вопрос Тарьяну о том, что из придуманных им алгоритмов с структур данных нравится ему больше всего. Оказалось, что это амортизированная оценка времени работы систем непересекающихся множеств. На изобретение СНМ с доказательством точной оценки ушло два или три года.

Comments

[griffon]

Надо бы видео посмотреть, а то так получилось, что единственный концерт Боба Дилана в России совпал с лекцией Андрея об этом.

Пол СНМ там такая история, что оценка NlogN всем была очевидна, потом кто-то придумал Nlog*N, а Тарьян доказал финальную оценку, построив примеры, на которых она достигается.

[griffon]

Да, я это тоже ретвитил. Шутки шутками, но похоже, что в известных алгоритмах фамилия Тарьян чуть ли не чаще всех встречается.