Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Анализ пирамидальной сортировки




Читайте также:
  1. Cоциологический анализ электорального процесса: проблемы и методы исследования, сферы применения результатов
  2. I. Коллективный анализ и целеполагание воспитатель­ной работы с привлечением родителей, учащихся, учите­лей класса.
  3. II. Рабочие определения, используемые при анализе литературного произведения
  4. O 6.Анализ и интерпретация результатов.
  5. PEST-анализ
  6. SWOT - анализ и его применение в маркетинговых исследованиях.
  7. Swot- Анализ
  8. SWOT-анализ
  9. SWOT-анализ 1 страница
  10. SWOT-анализ 2 страница

Пусть дерево массива на нижнем (нулевом) уровне содер-жит максимальное число вершин. Для построения пирамиды из произвольного дерева (первая часть алгоритма) обработать все вершины, начиная с первого уровня. Для обработки вершины на i-том уровне число сравнений пропорционально i. Число вершин на i-том уровне равно 2[log2N]-1 , а всего уревней m=[log2N], следовательно общее число сравнений определяется формулой

1*2[log2N]-1 + 2*2[log2N]-2 + … +m*2[log2N]-m = O(N).

Во второй части алгоритма последовательно обрабатывают-ся с N, N-1, … ,2 вершинами. Число сравнений для перестройки дерева, состоящего из i вершин, в пирамиду пропорционально [log2i], следовательно общее число сравнений

[log2N]+[log2(N-1)]+…+[log22] = O(N*log2N).

Т.о. порядок функции ВС алгоритма пирамидальной сорти-ровки O(N*log2N).

Быстрая сортировка выбором.Улучшить сортировку выбором можно, если после каждого прохода получать больше информации, чем просто идентификация минимального элемента.

Пример:

k1   k2   k3   k4   k5   k6   k7   k8    
10  
10

10 – элемент MaxInt.

k1*(N-1) – количество просмотров; log 2 N – высота бинарного дерева.

Мы проходим от корня к листу по тому пути, по которому шел минимальный элемент (шаг 2). Затем осуществляем модификацию бинарного дерева. Общее количество модификаций: k2*log 2 N * (N-1).

Алгоритм быстрой сортировки выбором:


Дата добавления: 2015-04-18; просмотров: 10; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2021 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты