Сложность, тестирование, особые случаи

Сложность

Для тренировки нужно написать 10000 строк кода. Для этого можно использовать сайты leetcode.com, codeforces.com

Сложность алгоритма - это порядок количества действий, которые выполняет алгоритм.

Если сложность $O(N)$ - это значит, что скорость алгоритма зависит напрямую от количества данных и такую сложность называют линейной. Например, обычный цикл от $1$ до $N$ .

Если в программе два вложенных цикла, каждый от $1$ до $N$ , тогда сложность составит $O(N^2)$ .

$O$ никак не зависит от константы.
$100*N = O(N), 2*N=O(N)$ . Здесь 2 и 100 - константы, не зависящие от размера входных данных. Константы не так сильно влияют на скорость алгоритма при больших параметрах.

Например, алгоритм, который работает за $O(100*N)$ будет работать лучше, чем $O(1*N^2)$ , поэтому константа не так принципиальна.

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

$O$ (O-большое) означает, что наш алгоритм работает не более, чем за столько действий сколько указано в скобках, например $O(N) = 10 * N$ - означает что найдется такое число, в нашем случае 10, что наш алгоритм гарантировано совершит не больше, чем 10 * N действий. Чем асимптотическая сложность ниже, тем лучше, тем быстрее решается.

Сравнение алгоритмов по асимптотической сложности имеет смысл проводить только для больших значений параметров, пока он маленький там может произойти, что угодно :).

Еще существует "пространственная сложность" - количество использованной памяти, сколькдополнительной памяти потребляет наш алгоритм. Памяти алгортим не может потребить больше чем он потратил времяБ потому что чтобы что то положить в ячейку памяти это тоже элементарная операция. Но иногда алгоритмы отличаются и по дополнительной памяти которую они употребляют.

Задача №1. Условие.

Дана строка в кодировке UTF-8.
Найти самый часто встречающийся в ней символ. Если несколько символов встречаются одинаково часто, то можно вывести любой.

Задача №1. Решение 1.

Переберем все позиции и для каждой позиции в строке еще раз переберем все позиции и в случае совпадения прибавим к счетчику единицу. Найдем максимальное значение счетчика.

Заводим внешние переменные для максимального количества повторений и для значения символа.

Внешний цикл сначала выбирает первый символ и далее проходит по строке и ищет сколько раз этот символ в ней встречается, запоминаем значение символа и количество повторений и сохраняем их во внешнюю переменную.

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

Сложность алгоритма: $O(N^2)$ , тк 2 вложенных цикла.

public static char maxRepeatableChar(String s) {
    int ansCount = 0;
    char ans = 0;

    for (int i = 0; i < s.length(); i++) {
        char nowChar = s.charAt(i);
        int nowCount = 0;

        for (int j = 0; j < s.length(); j++) {
            if (s.charAt(j) == nowChar) {
                nowCount += 1;
            }
        }

        if (nowCount > ansCount) {
            ansCount = nowCount;
            ans = nowChar;
        }
    }
    return ans;
}

Но есть более эффективное решение.

Задача №1. Решение 2.

Переберем все символы, встречающиеся в строке, а затем переберем все позиции и в случае совпадения прибавим к счетчику единицу. Найдем максимальное значение счетчика.

Получаем список уникальных букв через Set.

Проходим по нему в цикле и для каждой из букв запускаем цикл, который подсчитывает количество повторений для этой буквы.

Записываем в счетчик и возвращаем искомый символ.

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

public static char maxRepeatableChar(String s) {
    Set<Character> str = s.chars().mapToObj(e -> (char) e).collect(Collectors.toSet());

    char ans = 0;
    int ansCount = 0;

    for (Character now : str) {
        int nowCount = 0;
        for (int j = 0; j < s.length(); j++) {
            if (s.charAt(j) == now) {
                nowCount += 1;
            }
        }
        if (nowCount > ansCount) {
            ansCount = nowCount;
            ans = now;
        }
    }

    return ans;
}

Задача №1. Решение 3.

Заведем словарь, где ключом является символ, а значением - сколько раз он встретился.

Проходим в цикле по всем символам строки и если символ встретился впервые - создаем элемент словаря с ключом, совпадающим с этим символом и значением ноль. Далее для текущего символа в словаре прибавляем к элементу словаря с ключом, совпадающим с этим символом единицу.

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

Сложность алгоритма: $O(N + K) = O(N)$ , N - количество проходов пока формировали словарь, K - количество прохода только по (уникальным) ключам. Но так как K обычно меньше N то можно сказать что алгоритм выполняется за $O(N)$ .

public static char maxRepeatableChar(String s) {
    char ans = 0;
    int ansCount = 0;
    Map<Character, Integer> dict = new HashMap<>();

    for (int i = 0; i < s.length(); i++) {
        char now = s.charAt(i);
        if (!dict.containsKey(now)) {
            dict.put(now, 0);
        }
        dict.put(now, dict.get(now) + 1);
    }

    for (Character key : dict.keySet()) {
        if (dict.get(key) > ansCount) {
            ansCount = dict.get(key);
            ans = key;
        }
    }

    return ans;
}

Сравниваем затраченное время и память (дополнительную)

Решение	Время	Память
#1 Проход по строке для каждого символа	$O(N^2)$	$O(N)$ - так как храним только саму строку
#2 Проход по строке для каждого символа в множестве	$O(N*K)$	$O(N+K) = O(N)$ - храним строку и множество ( $K$ )
#3 Использование словаря	$O(N)$	$O(K)$ - храним только словарь из K элементов

Особые случаи

Сумма последовательности

В данном алгоритме не обязательно делать проверку на пустую строку так как и без этой проверки у нас выведется ноль.

public static int sequenceSum(String s) {
    int[] sequence = s.chars().toArray();
    int sequenceSum = 0;
    for (int i = 0; i < sequence.length; i++) {
        sequenceSum += sequence[i];
    }
    
    return sequenceSum;
}

Максимум последовательности

В этом алгоритме мы не можем задать начальное значение нулем, тк в массиве могут быть еще и отрицательные значения, поэтому необходимо добавить ночальную проверку на пустую строку и при выполнении алгоритма стартовому значению присвоить первое значение в массиве.

public static double sequenceMax(String s) {
    int[] sequence = s.chars().toArray();
    if (sequence.length == 0) {
        return Double.NEGATIVE_INFINITY;
    } else {
        int sequenceMax = sequence[0];
        for (int i = 0; i < sequence.length; i++) {
            if (sequence[i] > sequenceMax) {
                sequenceMax = sequence[i];
            }
        }
        return sequenceMax;
    }
}

Тестирование

При тестировании алгоритма нужно проверить:

тесты из условия (если есть)
общие случаи
особые случаи (все числа отрицательные, пустая последовательность)

Тесты для алгоритма на поиск максимума последовательности:

1 3 2 - общий случай (максимум в середине)
1 2 3, 3 2 1 - максимум по краям
1 1 1 - все элементы одинаковы
1 - один элемент
_ - пустая последовательность
-2 -1 -3 - все числа отрицательные

Советы по составлению тестов

Если есть примеры - реши их руками и сверь ответ. Если не совпадает, то либо правильных ответов может быть несколько, либо ты неправильно понял задачу;
Сначала составь несколько примеров и реши задачу руками, чтобы лучше понять условие и чтобы потом было с чем сравнить;
Проверь последовательность из одного элемента и пустую последовательность;
"Краевые эффекты" - проверь что программа работает корректно в начале и конце последовательности сделай тесты чтоы ответ находился на первом и на последнем месте последовательности;
Составь покрытие всех ветвлений, так чтобы был тест, который входит в каждый if и else;
Подбери тесты чтобы не было ни одного входа в цикл;
Один тест - одна возможная ошибка;

Вопросы

Что приоритетней оптимизация по памяти или по времени исполнения?

Чаще всего по времени исполнения, а если есть несколько алгориитмов с одинаковым временем то уже по памяти. Но бывают редкие задачи, где память играет решающее значение.

Почему в решение №3 мы использовали Set но не считали его асимптотическую сложность?

Добавление в Set происходит за $O(1)$ времени. Объяснение будет в следующих лекциях.

Как проверить алгоритм, если не знаешь где может быть ошибка?
1. пишем самый простой базовый алгоритм для решения задачи
2. пишем генератор маленьких массивов из случайных чисел
3. запускаем цикл и сравниваем ответ нашего алгоритма с ответом примитивного алгоритма

Смотрите также:

Сложность, тестирование, особые случаи