Общее (программирование)

Алгоритмическая сложность

Говорят, что если оценка есть $O(n),$ или $O(n^2),$ или … $O(n^a),$ где $a$ $-$ константа, то алгоритм называется полиномиальным (если показатель степени $n$ небольшой, то ещё и называется эффективным).

Ну, например, простейшая сортировка массива методом выбора имеет сложность $O(n^2).$ (Православные сортировки имеют сложность $O(n\times \log (n)).$) Что это означает? Что если мы будем увеличивать длину входа в $n$ раз, то количество операций, выполняемых компьютером, будет увеличиваться в $C\times n^2$ раз, где $C$ $-$ некая константа. Например, если увеличить $n$ в 5, 10, 20, 30, 40 раз, а $C=2,$ то количество операций будет увеличиваться в $2\times 5^2=50,$ $2\times 10^2=200,$ $2\times 20^2=800,$ $2\times 30^2=1800,$ $2\times 40^2=3200$ раз.

А вот если алгоритм имеет сложность $O(2^n),$ или вместо 2 любое другое константное основание, то его называют экспоненциальным (пример $-$ любой переборный алгоритм). Тогда, даже если $C=0.5,$ то при увеличении длины входа в 5, 10, 20, 30, 40 раз количество операций будет увеличиваться соответственно в $0.5\times 25=16,$ $0.5\times 2^{10}=512,$ $0.5\times 2^{20}=524288,$ $0.5\times 2^{30}=536870912,$ $0.5\times 2^{40}=549755813888$ раз. Что называется, почувствуйте разницу. Теперь, что такое вообще длина входа и количество операций, в чём их мерить? $n$ $-$ это биты, символы или количество строк? А количество операций $-$ это ассемблерные команды, количество шагов Машины Тьюринга, операторы C или что-то ещё? А вот в том-то и дело, что неважно, ведь у нас оценка не абсолютная, а асимптотическая, нам важно лишь, как меняется относительная скорость работы алгоритма по сравнению с относительным изменением количества входных данных, поэтому все эти конкретные коэффициенты попадут в это $O.$ Главное, какие команды мы обзовём элементарными. Ясно, что какой-нибудь метод list.sort() не тянет на элементарную. Как получить эту оценку? Правильный ответ $-$ подумать головой. И решить задачку: во сколько раз увеличится количество операций при увеличении длины входа в 10, 20, 30, 40 раз? и увидеть эту функцию $f(n).$ Иногда придётся доказать теорему. На практике обращают внимание на количество итераций циклов, на уровень вложенности циклов, и на вызовы функций, зависящих от n. Простой цикл for (int i = 0; i < n; i++) {...} (Си) даёт оценку $O(n),$ двойной цикл for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {...} (Си) уже $O(n^2),$ если их тела тривиальны и не зависят от $n.$ Если в теле циклов вызываются функции, которые сами по себе тоже зависят от $n,$ то это добавляет сложности и это тоже надо учитывать.

Тесты

Классификация по степени изолированности:

1. Unit test. Модульное тестирование - проверка на корректность отдельных модулей исходного кода, “первый бастион” на борьбе с багами. Идея в тестировании каждой нетривиальной функции. Недостаток $-$ сложно подобрать тесты для каждой ветви программы, выдерживает ли результат точность; качество моделирования определяется “на глаз”. Примеры тестов:
   1. Пустая картинка должна иметь размеры 0×0 и не выделять памяти.
   2. Создание пользователя с пустым именем должно вызывать исключение.
   3. Удаление элемента из середины списка должно уменьшать его размер на единицу.
   4. Генератор паролей должен создавать строку строго заданной длины.
   5. Интерполяция линейной функции в точках исходной сетки должна возвращать исходные значения.
   6. Перевод вектора в другую систему координат и обратно равен начальному вектору.
   7. Скалярное произведение двух перпендикулярных векторов должно возвращать ноль.
   8. Нормализация нулевого вектора должна вызывать исключение.
   9. Один шаг интегрирования для тела под действием постоянной силы должен давать приращение скорости $Fdt/m.$
2. Integration test. Интеграционное тестирование $-$ отдельные программные модули объединяются и тестируются в группе.
   1. Моделирование не запускается, если параметры нефизичны.
3. System test. Проверяют работу всей программы как чёрного ящика на реалистичных сценариях.
   1. Запуск всей программы с одинаковым seed для генератора случайных начальных условий должен приводить к бит-в-бит идентичным выходным файлам за два прохода.
   2. При моделировании сохраняется полная энергия / период колебаний равен аналитическому.
   3. Проверка устойчивости и точности метода при вариации шага по времени.

Классификация по заданию строения системы:

1. Static test. Статическое тестирование $-$ проверка инструментов кода без запуска, проверка документации.
2. Dynamic test. Динамическое тестирование $-$ запуск кода для проведения проверок. Здесь можно полагаться на физический смысл описываемых процессов, законы сохранения. Виды:
   1. White-Box test. Тестирование белого ящика $-$ тестирование ветвей, маршрутов, операторов.
   2. Black-Box test. Тестирование чёрного ящика $-$ метод тестирования программы без использования знания о внутреннем устройстве объекта. Примеры:
      1. Эквивалентное разбиение: «Целое число принимает значение от 0 до 999», «Первый символ должен быть заглавным».
      2. Анализ граничных значений. Если входные значения должны быть в интервале $[-\mathrm{1.0..}+1.0],$ проверяем $-1.0,1.0,-1.000001,\mathrm{1.000001.}$
      3. Анализ причинно-следственных связей.
      4. Предположение об ошибке (в значительной степени основан на интуиции). Идея метода состоит в том, чтобы составить список, который перечисляет возможные ошибки и ситуации, в которых эти ошибки могли проявиться.

Другие тесты:

1. Regression test. Регрессионное тестирование $-$ проверка того, как код работает после внесённых изменений.
2. Mutation test. Мутационное тестирование $-$ небольшие изменения кода программы. Состоит в выборе мутирующих операторов и применения их одного за другим к каждому фрагменту исходного кода программы. Мутирующим оператором называется правило преобразования исходного кода. Например:
   1. Удалить оператор программы.
   2. Заменить каждое логическое выражение на логическую константу «истина» или «ложь».
   3. Заменить каждую арифметическую операцию на другую. Например, + на *.
   4. Заменить каждую логическую операцию на другую. Например, > на >=.