Определить время работы алгоритма

307

27 августа 2017, 03:09

Решал задание: найти в массиве строк ту, в которой меньшее количество повторяющихся символов; но когда понадобилось определить скорость работы, запутался. Помогите пожалуйста разобраться, каково время работы данной реализации, и главное, почему? Спасибо.

public String getLessRepeatChars(@NotNull final String[] src) {
    if (src.length == 0) throw new IllegalArgumentException();
    String result = src[0];
    int tmp = getAmountDifferentCharsIn(src[0]);
    for (int i = 1; i < src.length; i++) {
        final int amount = getAmountDifferentCharsIn(src[i]);
        if (tmp > amount) {
            tmp = amount;
            result = src[i];
        }
    }
    return result;
}
private int getAmountRepeatCharsIn(@NotNull final String s) {
    final Map<Character, Integer> map = new HashMap<>();
    for (Character c : s.toCharArray()) {
        Integer amount = map.get(c);
        if (amount == null) {
            map.put(c, 1);
        } else {
            map.replace(c, ++amount);
        }
    }
    int result = 0;
    for (Integer val : map.values()) {
        if (val > result) result = val;
    }
    return result;
}

Буду признателен конструктивной критике по реализации, особенно в плане производительности.

Answer 1

Метод getAmountRepeatCharsIn

Возьмем за n длину строки s.
Сначала происходит подсчет всех символов в строке — происходит это за линейное время.
Затем ищется максимальное значение — это тоже происходит за линейное время.
Т.е функция getAmountRepeatCharsIn работает за O(n).

Метод getLessRepeatChars

Возьмем за m количество строк в массиве src. Выполняется проход по всем строкам, в каждой итерации которого вызывается getAmountRepeatCharsIn. Т.е. время работы всего алгоритма будет O(m*n), где m и n — это выше написано. (Чтобы быть точнее, то за n наверное даже стоит взять наибольшее из всех длин).
Ну личное мое мнение, что асимптотически этот алгоритм улучшить нельзя, потому что как минимум нужно прочитать всю информацию массива, что уже займет O(m*n).
Единственное, можно улучшить алгоритм в плане исправлений константных операций. (ну например, не обязательно каждый раз копировать строку, чтоб вернуть её. Можно хранить просто индекс, а потом вернуть нужную строку исходя из индекса).