Комментарии 10
новый метод приближается – но не совпадает – с показателями наилучшего из возможных в принципе алгоритмовполучается что сейчас это алгоритм ради алгоритма?
0
Я думаю, имеется в виду, что математически доказано, что лучший алгоритм имеет некую сложность, лучше, чем log(n) ^3 — например, log(n) ^2 (пишу наобум), но его пока не нашли. Из найденных у этого минимальная алгоритмическая сложность, проблема однако в том, что log(n)^3 становится хуже, чем sqrt(n) на довольно-таки больших n (миллионы или десятки миллионов), и с практической точки зрения это действительно делает алгоритм малоприменимым для реальных задач.
По крайней мере, я это понял так.
+4
НЛО прилетело и опубликовало эту надпись здесь
sqrt(1 000 000 000) = 31 622.7766
log(1 000 000 000) ^ 3 = ~30 ^ 3 = 27 000 (Это если log по основанию 2)
Тут нужно еще сравнивать алгоритмическую сложность единичной операции каждого метода. Количество операций различаются не очень сильно. Решает то, как быстро работают сами операции.
log(1 000 000 000) ^ 3 = ~30 ^ 3 = 27 000 (Это если log по основанию 2)
Тут нужно еще сравнивать алгоритмическую сложность единичной операции каждого метода. Количество операций различаются не очень сильно. Решает то, как быстро работают сами операции.
0
В нанотехнологических проектах это оказывается уже полезным практически.
0
В статье не упоминается важный контекст — для проверки планарности графа (и даже его вложимости в проективную плоскость) нужно линейное от числа вершин время. Поэтому для задачи проверки планарности графа после добавления к нему ребра ученые бьются за время быстрее линейного.
+2
Джейкоб Холм
Почему Джейкоб? Судя по фамилии (довольно распространённой в Скандинавии) он датчанин, поэтому Якоб. Да и фамилию стоит писать с мягким знаком, т.е. Хольм (ср. с Стокгольм, Борнхольм)
+1
Название классное для алгоритма
0
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Новый алгоритм проверки пересечений в графах прятался на виду