История изменений
Исправление i-rinat, (текущая версия) :
самый быстрый
Нет, этот метод имеет сложность O(N^2), потому что производится N итераций с большими числами, которые к концу алгоритма имеют количество цифр пропорциональное N.
Существуют методики вычисления, которые делают O(logN) операций, и поэтому имеют сложность O(N*logN).
upd. Скорее всего, там будет O(N*logN*logN*loglogN), но это не столь важно.
Исходная версия i-rinat, :
самый быстрый
Нет, этот метод имеет сложность O(N^2), потому что производится N итераций с большими числами, которые к концу алгоритма имеют количество цифр пропорциональное N.
Существуют методики вычисления, которые делают O(logN) операций, и поэтому имеют сложность O(N*logN).