Какова временная сложность выполнения этого кода?

Question

Я должен распечатать количество вхождений символов внутри строки. Я использовал что-то вроде:

String str="This is sample string";
HashSet<Character> hc= new HashSet<Character>();
for (int i = 0; i < str.length(); i++) {
    if(!Character.isSpaceChar(str.charAt(i))  && hc.add( str.charAt(i))  ) {
        int countMatches = StringUtils.countMatches(str, str.charAt(i));
        System.out.println(str.charAt(i)+" occurs at "+countMatches  +" times");
    }
}

Это своего рода решение, но как мне проанализировать сложность времени ? Я новичок, поэтому, пожалуйста, проведите меня через процесс обучения.

Answer 1

Прежде всего, если вы ищете достойное введение в анализ сложности, следующее выглядит довольно неплохо:

• Нежное введение в анализ сложности алгоритма от DionysisZindros.

Я рекомендую вам внимательно прочитать все и уделить время выполнению упражнений, встроенных в страницу.

---

Сложность вашего кода нетривиальный.

На первый взгляд, цикл будет выполняться N раз, где N - длина входной строки. Но затем, если мы посмотрим на то, что делает цикл, он может сделать одну из трех вещей:

1. , если символ является пробелом, ничего больше не будет сделано
2. , если символ не являетсяпробел, он добавляется (или повторно добавляется) к хэш-карте
3. , если был добавлен символ, вызывается countMatches.

Сложность бездействия O(1).

Сложность добавления записи на карту составляет O(1).

Сложность вызова countMatches равна O(N), потому что она просматривает каждый символ строки.

Теперь, если мы думаем о том, что делает код, мы можем легко определить лучшие и худшие случаи.

• Лучший случай происходит, когда все N символовстрока - это пробел. Это дает O(N) повторений O(1) тела цикла, давая сложность в лучшем случае O(N).

• Худший случай возникает, когда все N символов различны. Это дает O(N) повторений O(N) тела цикла, давая сложность наихудшего случая O(N^2). (Вы могли бы подумать ... но читать дальше!)

А как насчет среднего случая? Это сложно, если мы не знаем больше о природе входных строк.

• Если символы выбраны случайным образом, вероятность повторения символов мала, а вероятность пробелов невелика.
• Если символ представляет собой буквенный текст, то пробелы встречаются чаще, как и повторения. Действительно, для английского текста символы, скорее всего, будут ограничены прописными и строчными латинскими буквами (52) плюс несколько знаков препинания. Таким образом, вы можете ожидать около 60 записей карты для длинной строки и производительности, которая быстро сходится к O(N).

Наконец, даже наихудший случай не действительно O(N^2). Строка - это последовательность значений char, а значения Java char ограничены диапазоном от 0 до 65535. Таким образом, после 2 ^ 16 различных символов все символы должны повторяться, и поэтому даже наихудший случай переходит к O(N) как N уходит в бесконечность.

(я упоминал, что это было нетривиально? ?)

Answer 2

То, что вам нужно сделать здесь, это причина того, сколько шагов должно быть сделано в зависимости от длины строки.

Для каждого символа в строке он должен вызвать countMatches один раз. Каждый вызов countMatches должен повторять цикл над каждым символом строки снова, чтобы подсчитать их.

Другие операции (определение длины строки, добавление в HashSet, извлечение символа из строки по индексупроверка пробелов, печать ответов) предполагаются постоянными и не имеют значения.

Тот факт, что некоторые символы будут пропущены (поскольку они являются пробелами или уже есть в HashSet), не имеет значенияуменьшить сложность для неограниченной строки. Вы можете предположить наихудший случай, когда все символы различны.

Так что это O (n ^ 2), где n - длина строки.

Вы можете улучшить ее до O (n) изменив ваш HashSet на HashMap счетчиков. Тогда вам потребуется только один проход через строку вместо двух вложенных проходов.