Test algorithms

• Test algorithms
  • НОД - Наибольший Общий Делитель / GCD - Greatest Common Denominator
    • Идея алгоритма
    • Доказательство алгоритма GCD
  • Наименьшая сумма двух элементов в массиве / Lowest Sum of 2 elements
    • Идея алгоритма
  • Автотесты
    • GCD
    • Lowest Sum

НОД - Наибольший Общий Делитель / GCD - Greatest Common Denominator

Идея алгоритма

Вместо бесконечного сравнения каждого НОД каждой уникальной пары:

n, n-1, n-2, ... 1 = n(n+1)/2 = O(n^2)

Можно решить задачу гораздо проще - Находить НОД последовательно для каждого нового числа в списке и НОД предыдущей пары:

1. GCD[L, R] = gcd(n, n-1, ... 1)
2. gcd(gcd(n, n-1), ... 1)
3. gcd(gcd(gcd(n, n-1), n-2)... 1)
4. и т.д.

Соответственно у такой задачи асимптотика O(n)

Доказательство алгоритма GCD

Чтобы доказать правильность алгоритма, нужно доказать, что выполняется равенство gcd(a,b,c) = gcd(gcd(a,b),c)

Обозначим g = gcd(gcd(a,b),c) = gcd(d,c), где d = gcd(a,b)

1. g делит a,b,c (g | a,b,c):

   • d = gcd(a,b) ⇒ d | a и d | b.
   • g = gcd(d,c) ⇒ g | d и g | c.
   • Так как g | d и d | a,b ⇒ g | a и g | b. Значит g делит все три числа.

2. g — наибольший такой общий делитель:

   Пусть h — любой общий делитель a, b, c. Тогда h | a и h | b ⇒ h | d. Также h | c, значит h | gcd(d,c) = g. Следовательно любой общий делитель h не больше g (h делит g), т.е. g — наибольший.

Из 1) и 2) следует g = gcd(a,b,c). Поэтому gcd(a,b,c) = gcd(gcd(a,b),c). Аналогично для любого конечного множества чисел (ассоциативность свёртки по gcd).

Наименьшая сумма двух элементов в массиве / Lowest Sum of 2 elements

Идея алгоритма

Наименьшая сумма складывается из двух наименьших элементов в массиве - следовательно трудоёмкость от задачи перебора пар (как с НОД):

n, n-1, n-2, ... 1 = n(n+1)/2 = O(n^2)

Упрощается до задачи нахождения двух наименьших элемнтов с трудоёмкостью O(n)

Автотесты

Протестировать алгоритмы:

pytest -q

GCD

1. test_single_element — проверяет, что для одного элемента (индекс 0..0) возвращается само число (42).
2. test_two_elements — проверяет диапазоны длины 2 и единичный: gcd([14,15],0,1)=1 и gcd(...,1,1)=15.
3. test_all_zeros — проверяет, что диапазон всех нулей даёт 0, и одиночный ноль даёт 0.
4. test_negative_numbers — проверяет обработку отрицательных чисел: gcd([-6,9,-15],0,2)=3 и поддиапазон (0,1)=3.
5. test_mixed_zero_and_values — проверяет сочетание нуля и положительных: gcd([0,12,18],0,2)=6 и (1,2)=6.
6. test_early_exit_behavior — проверяет ранний выход при получении 1; SpyList фиксирует прочитанные индексы, ожидается, что чтение остановилось на индексе с 1.
7. test_invalid_ranges — проверяет, что некорректные диапазоны (L<0, R>=n, L>R) вызывают IndexError.
8. test_random_small_arrays — множество случайных проверок: результат сравнивается с наивной реализацией naive_gcd_range для случайных поддиапазонов.
9. test_large_values — проверяет работу с большими числами (10^18 и кратные), ожидаемый gcd = 10^18.
10. test_known_patterns — проверяет заранее известный шаблон (массив кратных 6): полный диапазон и поддиапазон оба дают 6.

Lowest Sum

1. test_empty_array_raises — проверяет, что для пустого массива функция выбрасывает ValueError.
2. test_single_element_returns_value — проверяет, что для массива из одного элемента возвращается этот элемент (7).
3. test_two_elements — проверяет поведение для двухэлементных массивов: порядок не важен и учитываются отрицательные значения (5+3=8, -2+10=8).
4. test_all_positive — проверяет обычный случай с положительными числами; два наименьших элемента 1 и 2 дают сумму 3.
5. test_with_negatives — проверяет работу с отрицательными числами; два наименьших (-5 и -3) дают сумму -8.
6. test_with_duplicates — проверяет случай с одинаковыми элементами; два минимальных 2+2=4.
7. test_sorted_input — проверяет корректность на уже отсортированных данных (по возрастанию и убыванию), ожидаемая сумма 1+2=3.
8. test_large_values — проверяет работу с большими числами (10**18 и близкими), ожидаемая сумма a + b.
9. test_random_small_arrays — обширная серия случайных проверок; результат сравнивается с наивной переборной реализацией по всем парам (учитывает случай длины 1).