Примеры алгоритмов и доказательств, которые кажутся правильными, но не являются

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

Существуют ли классические примеры алгоритмов, которые выглядят правильно, но не так? Я ищу случаи, когда подход Initialization-Maintenance-Termination улавливает то, чего нет на первый взгляд.

2D локальный максимум

вход: двумерный массив $n \times n$$A$

вывод: локальный максимум - пара такая, что A [ i , j ] не имеет соседней ячейки в массиве, который содержит строго большее значение. $(i,j)$$A[i,j]$

(Соседние ячейки есть среди , которые присутствуют в массиве.) Так, например, если является$A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$$A$

тогда каждая ячейка с полужирным шрифтом является локальным максимумом. Каждый непустой массив имеет хотя бы один локальный максимум.

Алгоритм. Существует алгоритм времени : просто проверьте каждую ячейку. Вот идея более быстрого, рекурсивного алгоритма.$O(n^2)$

Для определите крест X, состоящий из ячеек в среднем столбце и ячеек в среднем ряду. Сначала проверьте каждую ячейку в X , чтобы увидеть , если ячейка является локальным максимумом в A . Если так, верните такую ​​ячейку. В противном случае, пусть ( i , j ) будет ячейкой в X с максимальным значением. Поскольку ( i , j ) не является локальным максимумом, он должен иметь соседнюю ячейку ( i ′ , j ′ ) с большим значением.$A$$X$$X$$A$$(i, j)$$X$$(i, j)$$(i', j')$

Разбиение (массив A , минус ячейки в X ) на четыре квадранта - верхний левый, верхний правый, нижний левый и нижний правый квадранты - естественным образом. Соседняя ячейка ( i ′ , j ′ ) с большим значением должна находиться в одном из этих квадрантов. Назовите этот квадрант A ′ . $A \setminus X$$A$$X$$(i', j')$$A'$

Лемма. Quadrant ' содержит локальный максимум A .$A'$$A$

Доказательство. Рассмотрим начало с ячейки . Если это не локальный максимум, перейдите к соседу с большим значением. Это может повторяться до достижения ячейки, которая является локальным максимумом. Эта последняя ячейка должна быть в A ′ , поскольку A ′ ограничен со всех сторон ячейками, значения которых меньше значения ячейки ( i ′ , j ′ ) . Это доказывает лемму. $(i', j')$$A'$$A'$$(i', j')$$\diamond$

Алгоритм вызывает себя рекурсивно на подмассиваA',чтобы найти там локальный максимум(i,j), затем возвращает эту ячейку.$\frac{n}{2}\times\frac{n}{2}$$A'$$(i, j)$

Время работы для матрицы n × n удовлетворяет T ( n ) = T ( n / 2 ) + O ( n ) , поэтому T ( n ) = O ( n ) . $T(n)$$n\times n$$T(n) = T(n/2) + O(n)$$T(n) = O(n)$

Таким образом, мы доказали следующую теорему:

Теорема. Существует алгоритм времени для нахождения локального максимума в массиве n × n .$O(n)$$n\times n$

Или мы?