Смысл антимонопольного законодательства в том, что нельзя своё доминирующее положение на одном рынке использовать для получения конкурентного преимущества на другом рынке. Яндекс доминирует на рынке поиска и за счёт этого тащит себя вперёд на рынке новостей, объявлений и так далее. Как когда-то Microsoft доминировал на рынке операционок и использовал это для занятия рынка браузеров, или Google доминировал на рынке мобильных операционок и использовал для занятия рынка поиска.
Я думаю, то, как автор возвышается в своём бреду от ускорения сортировки до решения P vs. NP, игнорируя все просьбы предъявить осязаемые пруфы, могло бы дать задел интереснейшей диссертации по психиатрии.
Вы делите число из n бит на кусочки по √n бит. Представляете кусочки как коэффициенты полинома степени √n. Перемножаете полиномы. Преобразование Фурье требует как минимум O(√n log n) сложений (если быстро на корни из единицы умножать), стоящих √n, и потом нужно ещё √n умножений чисел из ≈√n бит. Эти умножения обрабатываются рекурсивно тем же алгоритмом. Возникает рекуррентная формула для оценки сложности: C(n) = n log n + √n C(√n). Разворачивая рекурсию, получаем n log n log log n, где множитель log log n отвечает за количество рекурсивных шагов.
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
Делят, по крайней мере вещественные числа, обычно методом Ньютона, а у него квадратичная сходимость, то есть требуется логарифмическое число шагов. А сложность шага пропорциональна сложности умножения.
Если в апи есть проблема, её надо обсуждать и находить пути решения. Главным образом этой статьёй я хотел узнать, один я ли вижу проблему или она действительно есть.
Ничего не поделать, дорогие хабровчане очень любят посты, в которых программисты самые умные, и очень не любят посты, в которых программисты не самые умные. Автор убедительно это доказывает нам уже целой серией своих постов (особенно предыдущим постом, ушедшим в минус). Автор, можно сказать, социальный экспериментатор.
Ну то есть насчёт скорости мы должны вам на слово поверить? Или самостоятельно для этого реализовать алгоритм, и ещё додуматься до упомянутых выше «интересных нюансов»?
В смысле очевидны? Сгенерируйте большой массив строк/чисел, отсортируйте их квиксортом и своим алгоритмом на одной и той же машине и покажите время выполнения в секундах.
Без сравнения секунд заверения про невероятную эффективность основаны ни на чём.
Зато сортировка слиянием даёт O(N log N). А если в квиксорте делать поиск медианы за O(N) для пивотирования, там тоже будет гарантированное O(N log N).
Хорошо, что вы эту фразу вынесли в самое начало статьи. Дальше, собственно, можно и не читать.
На самом деле оригинальная научная статья довольно неплохо разъясняет существующие алгоритмы (если вы не боитесь терминов «FFT» и «кольцо вычетов»).
(мягкий знак, Карл!) так оно и есть. Только где-то ещё имело место text recognition.
> ни одной ссылки на исследования
Без сравнения секунд заверения про невероятную эффективность основаны ни на чём.