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