Задача на декомпозицию, формулировка которой может направить по неверному пути. Есть квадрат со сторонами N, например, N = 5. У него есть диагональ, выделенная серым цветом. Нужно найти количество клеток на нижней половине, $cnt = f(N). Не обращайте внимание на рисунок, это просто визуализация для отвлечения внимания.
Типичный программист или кодер наверняка захочет попрограммировать и начнёт что-то придумывать, например, на циклах. Да, можно составить универсальный алгоритм поиска незакрашенной области. В худшем случае его вычислительная сложность будет доходить до O(n*n).
Человек с математическим или физическим бекграундом сразу увидит здесь формулу: $cnt = ($n * $n — $n) / 2. Сложность такого решения будет O(1) — идеально!
Однако, если задачу переформулировать примерно так: найти половину площади квадрата за вычетом диагонали, то даже школьник молниеносно её решит. Отсюда вывод, во многих задачах важна правильная формулировка и часто имеет смысл сделать переформулировку самостоятельно.
Ещё одним вариантом решения задачи будет подсчёт суммы натурального ряда от 1 до n-1, алгоритмическая сложность такого решения будет O(n-1).
И ещё один способ визуализации задачи на том же примере при N=5. Здесь невооружённым взглядом видна формула $cnt = (n — 1) / 2 * n, всё с той же сложностью O(1).
