Да, просто отдельно обработать какой-то случай предподсчитав его. Не обязательно лучший, просто какой-то. В результате этот случай станет лучшим и время его работы будет линейным (надо же сравнить входные данные).
Заодно тут ответ на вопрос, почему почти любой? Вы можете уменьшить время до линейного в одном случае. Поэтому, если алгоритм в лучшем случае работает не хуже чем за линейную сложность, то улучшить его таким образом не всегда можно.
Есть, правда спецэффекты, когда можно проверять только часть входных данных. Например для бинпоиска в массиве можно сравнить искомый элемент с первыми двумя, и найти ответ, если искомый элемент лежит где-то между ними.
Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.
