19. Порядковые статистики (Алгоритмы нахождения к-го наим. эл-та). Временная сложность алгоритмов.

 

С упорядочением тесно связана задача нахождения k-го наименьшего элемента в n-элементной последовательности.

            k-м наименьшим элементом в последовательности S с элементами a[1], a[2], ..., a[n] называется такой элемент b этой последовательности, что a[i].key<b.key не более чем для k-1 значений i и a[i].key<=b.key не менее чем для k значений i.

            Пример. В последовательности 3, 19, 4, 11, 6, 4, 11, 8, 11, 61 шестым, седьмым и восьмым наименьшими элементами будет 11.

            Очевидно, найти k-й наименьший элемент можно следующим способом: упорядочить последовательность в порядке неубывания ее элементов и взять k-й по порядку элемент (отсюда и название - порядковые статистики). Как следует из предыдущих параграфов этой главы, такой подход потребует O(n logn) сравнений. Аккуратно применяя стратегию “разделяй и властвуй”, можно найти k-й наименьший элемент за O(n) шагов.

            Основная идея эффективного подхода сходна с идеей быстрой сортировки:           в последовательности S выбирается главный элемент a[p]. Затем все элементы с ключами, меньшими a[p].key, размещаются в последовательности S1, элементы с ключами, равными a[p].key, размещаются в последовательности S2, а элементы с ключами, большими a[p].key, размещаются в последовательности S3. Сосчитав число элементов в последовательностях S1 и S2, можно узнать, в какой из них - S1, S2 или S3 - лежит k-й наименьший элемент:

                        ...

            if | S1|>k then продолжить поиск в S1 с тем же k

            else      if  | S1|+ | S2|>k then k-й наименьший элемент равен a[p]

                        else продолжить поиск в S3 с k:=k- | S1|-| S2|;

                        ...

            Остановимся подробнее на выборе главного элемента.

            I способ. Пусть на некотором шаге на вход процедуры поиска Selection поступила последовательность R, содержащая элементы с индексами от first до last. Тогда выбрать главный элемент можно с помощью генератора случайных чисел, необходимого для порождения целого числа p, first<=p<=last. Это число и определяет индекс главного элемента.

            При таком выборе главного элемента предложенный алгоритм в среднем работает очень быстро (Tmed(n)=O(n)). Однако неудачный выбор на каждом шаге главного элемента обуславливает плохой показатель максимальной сложности: Tmax(n)=O(n2).

            II способ. Последовательность S разбивается на подпоследовательности по 5 элементов в каждой.  Каждая подпоследовательность упорядочивается по ключу и из медиан этих подпоследовательностей составляется последовательность М. М содержит n/5 (целую часть от этого числа) элементов, поэтому ее медиану a[p] с ключом a[p].key:=m можно найти в 5 раз быстрее, чем у исходной последовательности. Медиана a[p] и выбирается в качестве главного элемента.

            При таком выборе не менее четверти всех элементов последовательности S имеют ключи, не большие m, и не менее четверти всех элементов этой последовательности S имеют ключи, не меньшие m (см. рис. 3.10). Матрица S на этом рисунке получена следующим образом: сначала отсортированы в порядке неубывания ключей все ее столбцы, после чего в том же порядке отсортирована третья строка.

            Рис. 3.10.

 

            Процедура Selection рекурсивно вызывается два раза, каждый раз на последовательности, длина которой равна некоторой части длины последовательности S. Чтобы предложенный алгоритм работал линейное время, сумма длин этих последовательностей должна быть меньше |S|. Именно поэтому исходную последовательность делят на 5 частей. Можно использовать и другие, отличные от 5, числа, но для некоторых из них процесс упорядочения последовательностей будет дольше.

            При втором способе выбора главного элемента k-й наименьший элемент находится за линейное время, т.е. Tmed(n)= Tmax(n)=O(n).