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

Эффективность алгоритма Быстр

Читайте также:
  1. III. Формы борьбы и эффективность действий антиглобалистов.
  2. Блок-схема алгоритма цикла с параметром представлена на рисунке 5.1.
  3. Блоки интегрального алгоритма
  4. Быстрая сортировка
  5. Быстродействие накопителя
  6. Быстрое реагирование
  7. Быстрый ручей звонко журчал в зарослях орешника.
  8. Влияние культуры на организационную эффективность.
  9. Вопрос 2. Экономическая эффективность осуществления природоохранных мероприятий.
  10. Время выдачи ответа баклабораторией при проведении бактериологического исследования для быстрорастущих микроорганизмов (время генерации 15-20 мин.)
  11. Выключатель быстродействующий (ВБ-630/1).
  12. Для правильного и быстрого выполнения задания

Алгоритм Быстрой сортировки имеет в среднем2) сложность N*log N и, следовательно, относится к улучшенным методам сортировки массивов (см. лекцию 4). Кроме того, даже среди улучшенных методов упорядочения Быстрая сортировка дает наилучшие результаты по времени (для относительно больших входных последовательностей - начиная с N = 100).

Конечно же, существует и итеративный вариант алгоритма Быстрой сортировки, который еще более эффективен. Мы предлагаем читателям построить его самостоятельно.

1) См. Д. Кнут. Искусство программирования для ЭВМ, любое издание. Т.1 Основные алгоритмы.
2) Существует, однако, "плохой" случай (и немногочисленные смежные с ним), когда эффективность Быстрой сортировки резко ухудшается до N2. Это происходит, если на каждом шаге срединным оказывается такой элемент, что от массива отделяется всего один элемент (массив длины N распадается на два массива длины N-1 и 1). Поэтому при описании эффективности мы использовали слова "в среднем".

 


1 | 2 | 3 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)