back to basics

[thedeemon]

А вот кто не поленился дочитать книжки про построение алгоритмов, вас там научили их строить? Вот есть такая простейшая задачка: дан массив из 8 чисел, нужно найти "почти самое маленькое" и "почти самое большое", т.е.

sort(xs); return (xs[1], xs[6]);

Надо это сделать за минимальное число действий. Под действиями подразумеваются сравнения, ну и копирования с перестановками, хотя сравнения важнее. На особенности современного железа и его наборов инструкций пока положим, интересует классический теоретический подход. Как положено подходить к решению? Массив можно менять на месте, можно использовать дополнительную память. Я знаю, как это сделать за 14 сравнений. Можно ли за меньшее число? Можно ли доказать, что за меньшее нельзя?

Comments

[gineer.livejournal.com]

\\Сейчас я умею доказывать, что менее чем 11 сравнениями не обойтись.

И есть реализация на 11 сравнений?
А то, это как бы известный эффект -- минимальная оценка есть, но как построить алгоритм её реализующий? ;)

[kgeorgiy.livejournal.com]

Конечно, нет -- эта оценка почти наверняка занижена.

На самом деле, описанный алгоритм нахождения второго минимума является оптимальным, что доказано, например, здесь (http://web.engr.illinois.edu/~jeffe/teaching/497/02-selection.pdf).
Если мы построим два отдельных дерева для минимума и максимума, то легко построить пример, когда они делают только независимые (то есть с непредсказуемым результатам) сравнения на всех уровнях, начиная со второго. При этом, 14 -- точная оценка.
Однако, потенциально, мы можем сделать смесь двух этих деревьев, и как их оценить в этом случае -- совершенно не понятно.

[kgeorgiy.livejournal.com]

Придумал, как поднять нижнюю границу до 13.
Пусть нам заранее известно, где находятся минимальный и максимальный элемент (это log(n)+log(n-1) бит). Тогда нам осталось найти минимум и максимум среди оставшихся n-2 чисел.
Найти минимум и максимум среди k чисел можно за 3k/2-2 сравнения. При k=n-2 получим 3n/2-5 сравнений.
В сумме получим 3n/2-5+log(n)+log(n-1) сравнений.

Итого имеем зазор в 1 (часто) или 2 (для специально подобранных n) сравнения.