В чем разница между тривиальным случаем, базовым случаем и крайним случаем?

Question

Я часто сталкиваюсь с этими терминами, когда говорю об алгоритмах.

Тривиальный случай

Базовый корпус

Кромка

Они все одинаковые? или есть какая-то существенная разница между ними?

Answer 1

«Тривиальный случай» - это случай, который простой ограниченный алгоритм все еще может решить. Например, случай, когда вам нужно отсортировать список чисел, но они уже отсортированы.

«Базовый случай» обычно используется в отношении рекурсии и относится к случаю, который обрабатывается напрямую, без какой-либо дальнейшей рекурсии. Например, быстрая сортировка одного элемента. (Базовые случаи обычно тоже тривиальны.)

«Крайний случай» - это случай, который в некотором роде необычен, который неправильно обрабатывается логикой, которая работает в большинстве случаев или которая приводит к особенно низкой производительности или результатам. Например, быстрая сортировка массива со всеми равными элементами делает невозможным выбор эффективного центра.

Answer 2

Поговорим о нижеприведенном алгоритме факториала

factorial (n) = n * factorial (n - 1) if n > 0
              = 1 if n is 0
              = error if n < 1

Тривиальный случай : Простые случаи, которые должны пройти, если алгоритм нормален. (По аналогии с тестом на дым) Обычно можно рассчитать это с помощью ручки или бумаги. Пример факториала (3) или факториала (5)
Базовый случай : Завершающее условие в рекурсии, к которому сходится алгоритм. в этом случае n равно 0.
Крайний случай : случаи, когда алгоритм может дать неправильный ответ из-за языкового ограничения (переполнение переменной, деление на ноль и т. Д.) Или случаи, когда алгоритм должен сообщать об ошибке изящно, а не разбивать.