Пятнашки глазами алгоритмиста. Часть 3: константная оценка точности

Часть 1: асимптотическая оценка сложности
Часть 2: думаем и улучшаем оценки!
Продолжаем рассматривать свойства алгоритма из первой задачки. Возникает естественный вопрос:


Начнём рассуждать.
На первый взгляд может казаться, что оценку получить нетрудно: ведь, как уже показано, в худшем случае минимальное решение имеет тот же порядок (относительно размера входа N), что и решение алгоритма.
Однако, как ни странно, в более “простых” случаях, когда количество ходов оптимального решения не так велико, алгоритм уже может существенно отставать (именно в относительном, а не в абсолютном плане).

Из начальной позиции сдвинем костяшки по краям “змейкой” на единицу.

Например,
01 02 03 04 05 06
07 08 09 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 ##
сдвигаем в
02 03 04 05 06 12
01 14 08 09 10 18
07 20 15 16 11 24
13 26 21 22 17 30
19 32 27 28 23 ##
25 31 33 34 29 35

Сумма расстояний до правильных мест теперь 6N - 8 = O(N). Такова и длина минимального решения.

Для выбора очередной костяшки для перемещений в правильную позицию алгоритму придётся делать проходы по каждой строке – как минимум O(N^2) ходов.

То есть, с увеличением N, алгоритм будет ошибаться не в константу, а в O(N^2)/O(N) = O(N) раз.
Конечно, можно попробовать выбирать, по строчкам или по столбцам начинать заполнение…


…но вот с таким примером уже всё равно никак не получится справиться, не изменив метод радикально.
//Сумма расстояний до правильных мест 10N+o(N) = O(N)

Значит ли это, что алгоритм “плохой”?..

Продолжение