Как стать автором
Обновить

Комментарии 10

новый метод приближается – но не совпадает – с показателями наилучшего из возможных в принципе алгоритмов
получается что сейчас это алгоритм ради алгоритма?

Я думаю, имеется в виду, что математически доказано, что лучший алгоритм имеет некую сложность, лучше, чем log(n) ^3 — например, log(n) ^2 (пишу наобум), но его пока не нашли. Из найденных у этого минимальная алгоритмическая сложность, проблема однако в том, что log(n)^3 становится хуже, чем sqrt(n) на довольно-таки больших n (миллионы или десятки миллионов), и с практической точки зрения это действительно делает алгоритм малоприменимым для реальных задач.
По крайней мере, я это понял так.

НЛО прилетело и опубликовало эту надпись здесь

Тьфу ты, да, я имел в виду, что становится лучше только начиная с больших значений n, и именно из-за этого слабо применим в реальных задачах. Спасибо за поправку.

sqrt(1 000 000 000) = 31 622.7766
log(1 000 000 000) ^ 3 = ~30 ^ 3 = 27 000 (Это если log по основанию 2)
Тут нужно еще сравнивать алгоритмическую сложность единичной операции каждого метода. Количество операций различаются не очень сильно. Решает то, как быстро работают сами операции.

На миллиарде да, разница небольшая и легко может быть полностью нивелирована разницей в сложности единичных операций. Но на триллионе разница почти в 16 раз. А на квадриллионе — в 256.
О том и речь, что на практике такие количества нечасто обрабатываются, мягко говоря.

В нанотехнологических проектах это оказывается уже полезным практически.
В статье не упоминается важный контекст — для проверки планарности графа (и даже его вложимости в проективную плоскость) нужно линейное от числа вершин время. Поэтому для задачи проверки планарности графа после добавления к нему ребра ученые бьются за время быстрее линейного.
Джейкоб Холм

Почему Джейкоб? Судя по фамилии (довольно распространённой в Скандинавии) он датчанин, поэтому Якоб. Да и фамилию стоит писать с мягким знаком, т.е. Хольм (ср. с Стокгольм, Борнхольм)

Название классное для алгоритма
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории