Боюсь, что в информатике (как и в математике в целом) все весьма конкретно: доказательство относится к данной теореме, формула - к данному алгоритму и т.д. Ожидать появление универсальной формулы для всех алгоритмов поиска столь же вероятно, как и единого доказательства всех теорем разом, в том числе и еще не сформулированных.
Одна универсальная точно не подойдет(для некоторых хорошо исследованных алгоритмов, типа быстрой сортировки).
Да и в чем тогда необходимость изобретения разных алгоритмов, если метрики у них все равно одинаковы?
Это зависит от природы используемых данных и начальных условий(приминительно к алгоритмам сортировки). Например, нужно отсортировать массив объектов; берем быструю сортировку - быстродействие в худшем случае O(n^2), для любых объектов подойдет. Но если исходный массив состоит из чисел, время можно улучшить до O(n).
...Но минимальный максимум - 3.
Сие понятие мне не знакомо, а спорить о неизвестных мне вещах не в моих правилах. Попытки поворошить в памяти университетский курс математики на предмет "минимального максимума" ничего не дали.
...
Если кто-то может мне толково объяснить, что такое этот самый "минимальный максимум" и чем он отличается от обычного максимума, буду очень благодарен.
Ок, берем несколько алгоритмов сортировки(рассматриваем кол-во k(n)сравнений в наихудшем случае, т.е. максимумы)
1) быстрая - k(n) = n^2
2) сортировка простым выбором - k(n) = 1/2(n^2-n)
3) для наглядности можно взять какой-нибудь 'страшный' алгоритм - k(n) = n^3
4) 'несуществующий' алгоритм - пусть нам известна формула для минимального кол-ва сравнений(о которой я говорил) и алгоритм ее реализующий. k(n) = c(n) =
Еще раз напомню что k(n) -
гарантированное кол-во сравнений, при помощи которых можно выполнить сортировку(в частных случаях возможно потребуется меньше).
Пусть дан массив из 5 элементов, тогда используя вышеперечисленные алгоритмы потребуется сравнений(
максимум)
1) - 25
2) - 10
3) - 125
4) формула неизвестна, но 5 объектов можно отсортировать за 7 сревнений.
таким образом минимальный из максимумов получится, если использовать алгоритм (4).
P.S. Неудачно выбрал термин...
