Данный алгоритм находит медиану 11 чисел в лучшем случае за 15 сравнений, а в худшем - за 20. Если рассмотреть все 11! = 39916800 перестановок 11 чисел, то получим следующую статистику: 15 - 86400 16 - 740160 17 - 2952000 18 - 7401600 19 - 12988800 20 - 15747840 В среднем получается 18.997 сравнений. В этот алгоритме последовательно определяются числа, которые больше или равны, чем 6 других, и эти числа отбрасываются. Из оставшихся 6 находится максимум - это и будет медиана. Данная реализация этого алгоритма содержит цикл, а значит и дополнительные сравнения ( переменной цикла, а не исходных чисел ). Но при желании цикл можно развернуть, поэтому эти сравнения не учитываются.Алгоритм реализован в виде шаблона-функции: template<class T> inline T _median11 ( const T * a ) ... Исходники находятся в файле median.h. Наверх |