1302
правки
Изменения
→Сложность
|}
===Сложность===
Данный алгоритм работает за <tex>0O(NlogN)</tex> действий и требует <tex>0O(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения 1ого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>0O(N+M)</tex> действий и требует <tex>0O(N+M)</tex> памяти, где <tex>M</tex> - размер алфавита.
===Псевдокод===
Пусть N - количество символов во входной строке, M - количество символов в алфавите, k - номер исходной строки в матрице перестановок, s - входящая строка, count - массив для сортировки подсчетом, t - вектор обратного преобразования.
