Технически, в худшем случае, временная сложность алгоритма будет O(N), но , почему это O(N), немного сложнее.Необходимо рассмотреть три операции.
Во-первых, toLowerCase() во входной строке.Это O(N) относительно длины строки, просто.
Во-вторых, первая .replace функция: .replace(/[^a-z0-9]/g, '').Это также O(N) - выполнить итерацию по всем символам и заменить не алфавитно-цифровые символы пустой строкой.
В-третьих, и самое сложное: тест /(.)[^\1]*?\1/g.Давайте сначала разберем это регулярное выражение.Обратите внимание, что \1 внутри набора символов , вероятно, не делает то, что вы думаете, - это не обратная ссылка, это соответствует символу Unicode в индексе 1, который является Start of Heading контрольный символ:
console.log(/[\1]/.test(String.fromCharCode(1)));
console.log(String.fromCharCode(1));
// not the sort of thing that would appear in an ordinary string, as you can see
Это не то, что вы хотите.Давайте исправим это для простоты - это не будет иметь никакого значения для сложности вашего алгоритма, поэтому давайте предположим, что вместо этого мы используем шаблон /(.).*?\1/.
Он будет захватывать первый символ вгруппа, затем ленивый - повторите любой символ, пытаясь найти символ, соответствующий первой группе снова.Движок регулярных выражений будет пытаться выполнить этот тест, начиная с первого символа в строке - если длина строки равна N, он будет начинаться с индекса 0 и перебирать значения от 0 до N - 1, проверяя, совпадают ли какие-либо символысимвол с индексом 0.Поскольку мы предполагаем наихудший случай, мы можем предположить, что это не удастся (дубликаты первого символа не найдены), и мы выполнили около N операций.Затем движок попытается сопоставить, начиная с индекса next , index 1, и будет перебирать каждый следующий символ до тех пор, пока не доберется до конца строки (N - 1), ищатот же символ совпадает с индексом 1. В худшем случае, это не удастся, мы только что выполнили около N - 1 операций, и движок перенаправит еще один символ, для индекса 2. См. образец?
Starting index ~Operations required to check this index ~Total operations
0 N N
1 N-1 2N-1
2 N-2 3N-3
3 N-3 4N-6
4 N-4 5N-10
...
N-1 1 N^2 - 0.5N^2
В худшем случае, в строке нет повторяющихся символов, и движок выполняет около 0.5N^2 шагов для выполнения всей функции .test.Это не точно, потому что есть некоторые издержки , связанные с соответствием захваченного символа, но это незначительно по сравнению с фактором N^2.Попробуйте это на regex101 - вы можете видеть, что ввод 62 буквенно-цифровых символов занимает 2203 шага, что не так далеко от 0.5 * 62^2 = 1922.
Итак, потому что это .testфункция имеет сложность O(N^2) в худшем случае, звучит так, как если бы алгоритм в целом имел сложность O(N^2), верно?Вообще-то, нет!Причина в том, что первый .replace(/[^a-z0-9]/g, '') гарантирует, что тестируемая строка будет содержать только строчные буквы и цифры (36 возможных символов).Это означает, что .test может выполнять итерацию не более 36 символов перед возвратом true - 37-й символ (или любой другой символ после этого) будет обязательно дубликатом одного из предыдущих символов,потому что есть только 36 возможных уникальных персонажей.Строка в худшем случае будет выглядеть примерно так:
0123456789abcdefghijklmnopqrstuvwxyzzzzzzzzzzzzzzzzzzzzzz...
, что потребует около 1072 * шагов, чтобы добраться до z s, найти, что они дублированы, и передать .test.Итак, наихудший случай для .test, с учетом ограниченного ввода , на самом деле O(N), а не O(N^2)!
Подводя итог: toLowerCase() равно O(N) в худшем случае..replace - O(N) в худшем случае.Наконец, .test - O(N) в худшем случае.Таким образом, сложность времени вашей функции составляет O(N) в худшем случае.
Все вышесказанное, хотя это может быть O(N), но все равно относительно неэффективно по сравнению с вашей другой реализацией, которая перебирает каждый символ в строке и добавляет его как свойство объекта, возвращаяtrue как только найден любой повторяющийся символ.