Python - Обоснование алгоритма

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

• Direct Proof:

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

• Proof by induction:

  Здесь мы начинаем с конкретного случая истины, а затем обобщаем его на все возможные значения, которые являются частью истины. Подход состоит в том, чтобы взять случай подтвержденной истины, а затем доказать, что это также верно для следующего случая для того же данного условия. Например, все положительные числа вида 2n-1 нечетны. Мы докажем это для определенного значения n, а затем докажем для следующего значения n. Это доказывает, что утверждение в целом истинно, путем доказательства индукции.

• Proof by contraposition:

  Это доказательство основано на условии, что если Not A влечет Not B, то A влечет B. Простой пример: если квадрат n четный, то n должно быть четным. Потому что если квадрат на n не четный, то n не четный.

• Proof by exhaustion:

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