Сферы программирования по сложности

Проектирование компьютерных программ может быть значительно упрощено путем организации информации в абстрактные структуры данных (ADS) или абстрактные типы данных (ADTS). Например, можно смоделировать таблицу чисел. Имеющую три столбца и неопределенное число строк. В терминах массива с двумя измерениями: (1) большое число строк и (2) три столбца. Ключевой особенностью современных компьютерных программ является возможность манипулировать рекламой с помощью процедур или методов. Заранее определенных программистом или разработчиком программного обеспечения. Это требует. Чтобы структуры данных были определены тщательно. Продуманно и подробно.

Этот раздел организован следующим образом:

    1.1. Введение и обзор
    1.2. Обзор понятий дискретной математики и нотации
    1.3. Обзор языка программирования Java
    1.4. Обзор нотации сложности
    1.5. Рекурсивные вычисления
    1.6. Массивы и списки
    1.7. Поиск, Выбор и сортировка

В этом классе мы сосредоточимся только на структурах данных. Называемых массивами, списками, стеками, очередями, кучами, графамии деревьями. Чтобы рассмотреть темы и алгоритмы. Рассматриваемые в этом классе. Мы представим каждую структуру данных в терминах объединяющего формализма. А именно ADT и связанные с ним операции. Называемые последовательностью ADT.

Затем мы обсудим понятия дискретной математики и нотации. А также представим обзор языка программирования Java. Который является языком выбора для этого класса. Это поможет вам установить базовые знания в области теории и языков программирования. Необходимые для успешного завершения проектов.

Анализ сложности является важным инструментом конструктора алгоритмов. Который мы обсуждаем достаточно подробно. Чтобы позволить анализировать алгоритмы. Представленные в этом классе. Мы также обсуждаем использование рекурсии и технику анализа сложности рекурсивных отношений. Рекурсия является важным компонентом многих современных программных систем. Программ и модулей. Мы увидим, что дизайн рекурсивных программ несколько отличается от линейного. Последовательного потока управления. К которому вы привыкли в программировании начального уровня. Таким образом. Рекурсивные отношения необходимы для проанализируйте этот другой метод программирования таким образом. Который решительно отличается от анализа алгоритмов с линейным. Последовательным потоком.

Массивы и списки-это простые структуры данных. Которые облегчают широкий спектр операций с АЦП и. Таким образом. Формируют основу для разработки и реализации современных алгоритмов и программного обеспечения. Чтобы найти данные. Хранящиеся в массивах или списках. Мы выполняем операцию. Называемую поиском. Когда этот процесс связан со статистикой порядка (например. Нахождение медианы последовательности). Это иногда называют отбором Чтобы облегчить эффективный поиск. Мы должны иметь возможность сортировать числа или строки (последовательность символов). По которым мы хотим искать. В случае действительных чисел сортировка означает. Что числа расположены в порядке возрастания величины.

1.1. Введение и обзор

Чтобы установить надлежащий контекст для этого класса. Который связан с низкоуровневыми механизмами. Способствующими хорошему проектированию программного обеспечения. Мы начнем с обсуждения принципов проектирования программного обеспечения и проектирования.

1.1.1. Цели проектирования и инжиниринга программного обеспечения

Проектирование программного обеспечения можно разделить на два уровня. Разработка и анализ программного обеспечения высокого уровня направлены на создание правильногои эффективного программного обеспечения. На низком уровне мы больше озабочены надежностью, адаптивностьюи возможностью повторногоиспользования .

1.1.1.1. Цели Проектирования Программного обеспечения Высокого уровня. Для создания программ. Которые работают. Как указано для всех экземпляров ввода. Следующие цели проектирования должны быть достигнуты на высоком уровне:

Корректность-структура данных или алгоритм предназначен. На высоком уровне. Чтобы работать. Как указано для всех возможных входов.

Пример: Алгоритм сортировки должен располагать свои входные данные только в порядке возрастания или убывания.

Эффективность подразумевает (а) быстрое время выполнения и (б) минимальное использование вычислительных ресурсов.

Пример. Разработка алгоритмов для систем реального времени-это не просто вопрос использования быстрого оборудования. Необходимо создавать быстрые алгоритмы. Которые могут использовать преимущества коммерческого готового оборудования (COTS) для снижения себестоимости производства.

1.1.1.2. Цели Проектирования Программного Обеспечения Низкого уровня. Правильно разработанные и функционирующие программы должны достигать следующих целей в рамках реализации:

Робастность-программа производит правильные выходные данные для всех входов на любой аппаратной платформе. На которой реализована программа.

Робастность включает в себя понятие масштабируемости-способность структуры данных или алгоритма обрабатывать расширяющийся размер входных данных. Не вызывая чрезмерной сложности или вызывая неточность или сбой.

Адаптивность-программное обеспечение должно быть способно изменяться или эволюционировать с течением времени в соответствии с изменениями окружающей среды (например. Увеличение скорости процессора. Реализация клиент-сервер или новые функциональные возможности для увеличения рыночного спроса).

Пример. Проблема 2000 года является прекрасным примером плохого проектирования программного обеспечения. Когда поля даты в старом программном обеспечении (также называемом

устаревшим кодом) не были разработаны достаточно большими. Чтобы вместить коды дат в течение интервала. Превышающего 100 лет.

Повторное использование-данный раздел или фрагмент кода должен быть способен использоваться в качестве компонента в различных системах или в различных областях приложений без существенных изменений.

Апгрейды существующих программных систем должны быть просты в разработке и реализации. Но часто это не так из-за специфического и плохо спроектированного программирования.

Для достижения вышеперечисленных целей объектно-ориентированное программирование эволюционировало от процедурного и функционального программирования.

1.1.1.3. Принципы объектно-ориентированного проектирования помогают программисту или разработчику программного обеспечения организовать структуру и функциональность кода или программ в соответствии с несколькими руководящими принципами. Которые включают:

  1. Абстракция-Нужно уметь перегонять сложную систему в простое, краткое. Ясное описание структуры и функциональности системы.

    Пример. Операции

    Наблюдение. Применение принципа абстракции к структурам данных приводит к созданию абстрактных типов данных (ADT).

    Определение. АДТ-это математическая модель структуры данных. Которая определяет (а) тип хранимых данных и (б) операции над хранимыми данными с указанием типов параметров в операциях. В частности. ADT определяет. Что делает каждая операция. Но не обязательно. Как работает данная операция.

    Пример. В Java ADT моделируется как интерфейс, реализованный как класс. Классы определяют. Как должна выполняться данная операция с данными ADT.

    Определение. Класс Java реализует интерфейс тогда и только тогда. Когда методы класса включают методы интерфейса. Обратите внимание. Что данный класс может реализовывать несколько интерфейсов.

  2. Инкапсуляция-различные компоненты программной системы должны реализовывать абстракцию. Не раскрывая внутренних деталей реализации. Это называется сокрытием информации.

    Например, Меню Редактирования в текстовом процессоре полностью полезно без того. Чтобы пользователь знал. Как работают процессы вырезания и вставки.

    Преимущества инкапсуляции включают в себя:

    Свободная связь между классами-программисту нужно только соответствовать спецификации интерфейса. А не беспокоиться о деталях функциональности данного метода.

    Адаптивность-код может быть изменен без отрицательного влияния на функциональность программы. Благодаря наличию единого интерфейса.

  3. Модульность-наличие организационной структуры. Которая разделяет системы sfotware на функциональные единицы на основе иерархических отношений.

    Два вида иерархических отношений включают отношения has-a и is-a. Отношение has-a индуцирует иерархию компонентов. Подобную той. Что показана на рис.1. Здесь дверь, окно. Стена и пол являются составными частями здания. Отношение is-a индуцирует иерархию членства, подобную той. Что показана на рис .2, где жилое или коммерческое строение являются экземплярами более общего типа строения. Называемого зданием.


    Рис. 1.1.1. Иерархия компонентов на основе отношения has-a.


    Рис. 1.1.2. Иерархия членства на основе отношения is-a.

    Преимущества модульности и иерархического проектирования включают в себя:

    Группировка общих функций на самом общем уровне.

    Просмотр специализированного поведения и атрибутов как расширений одного или нескольких общих случаев. Также называемых наследованием.

1.1.1.4. Методы Объектно-Ориентированного Проектирования. Для реализации парадигм объектно-ориентированного проектирования были разработаны следующие методы. Доступные в большинстве объектно-ориентированных языков. Таких как C++ и Java:

Классы и объектыакторы в парадигме объектно-ориентированного программирования (ООП). Которые имеют методы, являющиеся действиями. Выполняемыми объектами. Классы и объекты облегчают абстракцию и. Следовательно. Устойчивость.

Интерфейсы и строгая типизация облегчают эффективную интерпретацию или компиляцию исходного языка без запутанных двусмысленностей. Это облегчает инкапсуляцию и. Следовательно. Адаптивность.

Наследование и полиморфизм позволяют данному объекту или подклассу специализировать атрибуты или возможности родительского класса. Например, на рисунке 2 небоскреб специализируется на описании офисного здания. Полиморфизм относится к способности данной операции или метода допускать различные типы операндов. Которые являются специализациями описания класса более высокого уровня. Наследование и полиморфизм облегчают модульность и возможность повторного использования. Когда описания классов доступны разработчикам и программистам.

Мы подробно рассмотрим каждое из этих понятий следующим образом.

  1. Классы и объекты являются строительными блоками объектно-ориентированного проектирования и программирования

    Определение. Объекты-это акторы в парадигме ООП.

    Определение. Класс-это спецификация переменных data fieldsinstance. Которые содержит класс. А также те операции. Которые класс может выполнять.

    Понятие ссылки: При создании объекта интерпретатор или компилятор ООП (1) выделяет память для данного объекта и (2) привязывает переменную к объекту. Где переменная. Как говорят, ссылается на объект.

    Взаимодействие. Класс или метод может либо (а) выполнять один из методов объекта. Либо (б) искать поля объекта.

    Наблюдение. В ООП объекты взаимодействуют с передачей сообщений. Например, два объекта o1 и o2 могут взаимодействовать через o1, запрашивая o2, чтобы:

    1. Напечатать описание самого себя,
    2. Преобразуйте o2 в строковое представление или
    3. Возвращает значение одного из полей данных o 2.

    В качестве альтернативы o1 может получить доступ к полям o2напрямую, но только в том случае. Если o2 дал o1 разрешение на такой доступ. Это пример сокрытия информации.

  2. Интерфейсы и сильная типизация.

    Наблюдение. Каждый класс должен slecify интерфейс прикладного программирования (API). Который он представляет другим объектам. Подход ADT заключается в том. Чтобы указать интерфейс как определение типа класса и набор методов для этого типа. Где все аргументы для каждого метода должны иметь определенные типы.

    Примечание. Жесткие спецификации типов (строгая типизация) жестко применяются интерпретатором или компилятором. Что требует строгого сопоставления типов во время выполнения.

    Примечание: Эта инкапсуляция достигается ценой работы программиста.

  3. Наследование и полиморфизм.

    Наблюдение. Наследование включает в себя разработку высокоуровневых классов. Которые могут быть специализированы на более конкретных описаниях классов.

    Пример. Номер класса Java может быть специализирован на float, integer, doubleили long.

    Определение. Базовый класс или суперкласс-это самый общий класс.

    Наблюдение. Специализированные классы или производные классы наследуют базовые свойства или методы от общего класса. Которые специализированы для данного подкласса. Рисунок 3 иллюстрирует эту концепцию для общего класса животных, который может включать подклассы собаки, лошадии человека, среди прочих.


    Рис. 3. Вывод подклассов с помощью методов. Также полученных из суперкласса Животных.

    Определение. Полиморфизм относится к способности объекта принимать различные формы.

    Пример. Ссылочная переменная v ссылается на объект o, но должна определить, к какому классу C ей разрешено ссылаться.

    Если класс D расширяет класс C (что показано на рис. 3), то v может ссылаться на любой класс D.

    Когда o ссылается на объект из класса D. Он выполняет метод o.bark(), o.neigh(), o.talk ()или o.sing (), в зависимости от обстоятельств. В этом случае D. Как говорят, переопределяет метод b() из класса C.

    Когда o ссылается на объект класса D. Он выполняет метод o.make-noise(), поскольку объектно-ориентированный интерпретатор или компилятор выполняет поиск от наиболее специфичного к наиболее общему классу. Таким образом, о может быть полиморфным.

    Наблюдение. Этот вид функциональной организации позволяет специализированному классу D:

    1. Расширить класс (например. C на рис. 3),
    2. Наследование универсальных методов от C и
    3. переопределите другие методы из C для учета специфических свойств объектов в D.

    Замечание. Метод, который обрабатывает сообщение для вызова данного метода. А затем находит этот метод. Называется динамическим алгоритмом отправки.

    Определение. Сигнатура метода-это комбинация имени метода вместе с типом и количеством аргументов. Переданных методу.

    Реализация. Java предоставляет разбавленный вид полиморфизма . Называемый перегрузкой, где даже один класс D может иметь несколько методов с одинаковым именем. При условии. Что каждый метод имеет различную сигнатуру.

    Наблюдение. Наследование. Полиморфизм и перегрузка методов поддерживают возможность повторногоиспользования .

1.1.2. Абстрактные структуры данных и ADT

Цель абстрактной структуры данных (ADS) состоит в том. Чтобы сократить семантический разрыв между программными конструкциями пользователя или прикладным программным обеспечением и вычислительным оборудованием (иначе известным как голая машина).

Когда экземпляры данного ADS могут быть построены из описания более высокого уровня (например. Определение класса Java). То мы говорим. Что такие экземпляры имеют заданный абстрактный тип данных (например. Массив, список. Стек)…) В этом классе мы будем изучать несколько ADT. Но каждый из них будет иметь общий набор общих операций. Которые обсуждаются следующим образом.

1.1.3. Последовательность ADT

Существует более или менее общий набор операций. Которые могут быть выполнены на каждом ADT. Который мы перечислим следующим образом. Здесь предполагается заданный ADT (например. Текущий класс). Значение в элементе ADT обозначается x, а положение элемента ADT в многоэлементном ADT обозначается

isFull() возвращаетTrue, если ADT не может содержать больше данных, и Falseв противном случае.

isEmpty() возвращаетTrue, если ADT не содержит данных, и Falseв противном случае.

Size() возвращает целое число. Большее или равное нулю. Которое обозначает количество элементов в ADT.

PositionOf(x) возвращает целое число или координату. Обозначающую положение первого экземпляра x, обнаруженного при поиске элементов ADT в заданном порядке сканирования.

ValueAt(i) возвращает значение i-го элемента в ADT.

InsertValue(x,i) вставляет значение x в ADT с помощью следующих шагов:

  1. Создайте новый элемент типа. Совместимый с ADT.
  2. Свяжите элемент с другими элементами в ADT. Сделав новый элемент i-м элементом и сделав все последующие элементы индексами (например. I+1, i+2 и т. Д.), которые следуют за индексом нового элемента в порядке приоритета. Присущем определению ADT.

  3. Поместите значение x в новый элемент.

ReplaceValueAt(i,x) помещает значение x в i-й элемент ADT. Не нарушая порядка элементов в ADT.

DeleteElement(i) удаляет i-й элемент ADT. Восстанавливая свойство order ADT. Это существенно меняет порядок шагов. Используемых в операции InsertValue.

OutputADT обычно записывает ADT на диск либо как объект на родном языке программирования (например. Сериализация объектов Java). Либо как строковое представление ASCII.

Обратите внимание. Что все предыдущие методы могут не использоваться с данным ADT. Например. Массив не облегчает простую вставку или удаление его элементов. Но список делает это.

1.1.4. Представление ADTS на языке программирования

В Java. Который является языком выбора для этого класса. Мы представляем каждый ADT как класс. В более ранних языках. Таких как FORTRAN. Было фиксированное количество типов данных. Которые не могли быть изменены. В PASCAL можно было заранее определить типы данных. Но были ограничения на то. Какие типы данных могут содержать. Этот процесс определения стал более гибким в языке Си. А инкапсуляция определений классов и методов объединила более ранние различия

Стоит отметить. Что некоторые языки до ПАСКАЛЯ имели очень гибкие. Но своеобразные определения типов данных. SNOBOL, ранний язык обработки строк. Имел очень гибкую систему определения ADT и мощный язык сопоставления шаблонов. Который можно было настроить (хотя и с некоторыми усилиями) для поиска данных. Хранящихся в ADT. PL/1 сделал несколько слабых попыток более гибких определений типов данных. Но был слишком большим языком. Чтобы быть полезным на практике. И умер неоплаканной смертью после нескольких пересмотров.

1.2. Обзор понятий и обозначений дискретной математики

Этот обзор приведен в Приложении Аи , таким образом. Не воспроизводится здесь.

1.3. Обзор языка программирования Java

Подробный обзор Java с учебными пособиями организован в иерархической форме в Приложении B и. Таким образом. Не воспроизводится здесь. Кроме того, учебник доктора Краммера по Java-это хорошее место для начала программирования на Java. Дополнительные учебники и ссылки приведены по этой ссылке.

1.4. Обзор нотации сложности

В этом разделе мы обсудим некоторые понятия сложности. В том числе обозначение Big-Oh.

Полезно иметь возможность указать сложность функции или алгоритма, то есть то. Как изменяется его вычислительная стоимость в зависимости от размера входных данных.

Предыстория и применение. Анализ сложности является ключом к разработке эффективных алгоритмов. Обратите внимание. Что требования к работе или хранению (памяти) данного алгоритма могут варьироваться в зависимости от архитектуры (процессора). На котором работает алгоритм. А также типа используемого программного обеспечения (например. Модули времени выполнения. Созданные из компилятора FORTRAN или C++). Таким образом. Анализ сложности имеет тенденцию быть приблизительной наукой и будет представлен в этом разделе.

В частности. Когда мы анализируем сложность алгоритма. Мы заинтересованы в установлении границ работы. Пространства или времени. Необходимых для выполнения вычислений. Заданных алгоритмом. Поэтому мы начнем наше изложение анализа сложности с анализа верхней границы роста функции.

Представление. O(x2) читает Big-Oh из x-квадрата) используется для указания верхней границы сложности функции f. Граница задается в терминах другой функции g и двух ограничений, C и k.

Определение. Пусть f,g : RR-функции. Мы говорим. Что f(x) = O(g(x)). Если существуют константы C, k R такие, что

| f(x) | C · | g(x) | ,

Пусть f = x3 + 3x 2 . Если С = 2, то

| f(x) | = | x3 + 3x2 | 2 · | x3 | ,

f(x) = O(g(x)).

В следующем разделе мы обсудим состав оценок big-Oh. Чтобы определить верхнюю границу сложности составных функций и алгоритмов.

1.4.1. Алгоритмы и алгоритмическая сложность

Начнем с того. Что в этом разделе мы используем алгоритмы для введения основных понятий и концентрируемся на анализе производительности алгоритмов. Особенно вычислительной сложности.

Определение. Алгоритм-это конечный набор инструкций для выполнения вычисления или решения задачи.

Рассмотрены типы алгоритмов. В этом курсе мы сосредоточимся на нескольких различных типах относительно простых алгоритмов, а именно:

Выбор — Поиск значения в списке. Подсчет чисел;

Сортировка-Упорядочивание чисел в порядке возрастания или убывания значения;

Сравнение-Сопоставление тестового шаблона с шаблонами в базе данных .

Свойства алгоритмов Полезно. Чтобы алгоритм обладал следующими свойствами:

Входные данные-Значения. Принятые алгоритмом. Называются входными данными или аргументами.

Результат, полученный алгоритмом. Является решением проблемы. Для решения которой он предназначен.

Определенность-Шаги в данном алгоритме должны быть четко определены.

Корректность-Алгоритм должен выполнять задачу. Для выполнения которой он предназначен. Для всех входных комбинаций.

Конечность-Вывод производится алгоритмом после конечного числа вычислительных шагов.

Эффективность-Каждый шаг алгоритма должен быть выполнен точно. За конечное время.

Общность-Процедура. Присущая конкретному алгоритму. Должна быть применима ко всем алгоритмам одной и той же общей формы. С разрешенными незначительными модификациями.

Для того чтобы облегчить разработку эффективных алгоритмов. Необходимо оценить границы сложности алгоритмов-кандидатов.

Представление. Сложность обычно представляется с помощью следующих мер. Которые нумеруются в том порядке. В котором они обычно вычисляются разработчиком системы:

Работа W(n) — Сколько операций каждого заданного типа требуется алгоритму для получения заданного выхода при заданных n входах?

Пространство S(n) — Сколько памяти (памяти или диска) требуется алгоритму для получения заданного выходного сигнала при заданных n входах?

Время T(n) — Сколько времени требуется для вычисления алгоритма (с n входами) на данной архитектуре?

Стоимость C(n) = T(n) · S(n)-Иногда называемая продуктом пространственно-временной полосы пропускания, эта мера говорит разработчику системы. Какие затраты совокупных вычислительных ресурсов требуются для вычисления данного алгоритма с n входами.

Анализ алгоритмической сложности в общем случае протекает следующим образом:

Шаг 1. Разложите алгоритм на шаги и операции.

Шаг 2. Для каждого шага или операции определите желаемые меры сложности. Обычно используя нотацию Big-Oh или другие типы границ сложности. Обсуждаемые ниже.

Шаг 3. Составьте компонентные меры, полученные на шаге 2, с помощью теорем. Представленных ниже. Чтобы получить оценку сложности(ов) для всего алгоритма.

Рассмотрим следующую процедуру нахождения максимума последовательности чисел. Оценка потребности в работе дается справа от каждого заявления.

 Пусть {an} = (a1,a2,...,an) { max = a1# Одна операция ввода-вывода для i = 2 до n do: # Цикл повторяется n-1 раз { если ai max, то # Одно сравнение на итерацию макс := ai# Может быть. Одна операция ввода-вывода } 

Анализ. (1) В предыдущем алгоритме мы отмечаем. Что в цикле существует n-1 сравнений. (2) В случайно упорядоченной последовательности половина значений будет меньше среднего, и1 будет считаться средним значением (для целей анализа). Следовательно, для замены значения на i потребуется в среднем n/2 операций вводаmax-вывода . Таким образом. Существует n/2 + 1 операций ввода-вывода. (3)Это означает. Что предыдущий алгоритм O(n) в сопоставлениях и операциях ввода-вывода. Точнее, мы утверждаем. Что в среднем случае:

W(n) = n-1 сравнений + (n/2 — 1) операций ввода-вывода.

Упражнение. В худшем случае было бы n операций ввода-вывода. Почему это так? Подсказка: Это может быть вопрос викторины или экзамена.

Полезные Термины. Когда мы обсуждаем алгоритмы. Мы часто используем следующие термины:

Tractable — Алгоритм принадлежит классу P. Так что алгоритм разрешим за полиномиальное время (отсюда и использование P для полинома). Это означает. Что сложность алгоритма равна O(nd), где d может быть большим (что обычно подразумевает медленное выполнение).

Трудноразрешимый-Рассматриваемый алгоритм требует большего. Чем полиномиальная работа, время. Пространство или стоимость. Приближенные решения таких алгоритмов часто более эффективны. Чем точные решения. И в таких случаях предпочтительны.

Разрешимый-Существует алгоритм. Который генерирует решение проблемы. Рассматриваемой алгоритмом. Но алгоритм не обязательно поддается обработке.

Неразрешимо-Не существует алгоритма для решения данной задачи. Пример: Тьюринг показал. Что невозможно решить. Завершится ли программа на заданном входе.

Класс NP-Если проблема находится в классе NP (неполиномиальная). То никакой алгоритм с полиномиальной наихудшей сложностью не может решить эту проблему.

Класс NP-Complete-Если какая-либо задача находится в классе NP-Complete. То любой алгоритм полиномиального времени. Который может быть использован для решения этой задачи. Может решить все NP-полные задачи. Кроме того, общепризнано. Но не доказано. Что ни одна NP-полная задача не может быть решена за полиномиальное время.

1.4.2. Нотация Big-Oh и связанные с ней тождества.

Ранее мы уже определили обозначение Big-Oh. В этом разделе мы приводим тождества для нотации Big-Oh. Которые позволяют вычислять оценки сложности составных функций с примерами.

Теорема 1. (Полиномиальное доминирование) Если f(x) = anxn , то f(x) = O(xn).

Пример. Найдите оценку сложности Big-Oh для n!

    Обратите внимание. Что n! = 1 · 2 · 3 · … · н н · н · н · … · n (n раз) = nn.

    Следовательно. N! = O(nn) .

Теорема 2. (Аддитивная комбинация) Если f1(x) = O(g1(x)) и f2(x) = O(g2(x)), то

(f1 + f2)(x) = O(max(g1(x), g2(x)) .

Теорема 3. (Мультипликативная комбинация) Если f1(x) = O(g1(x)) и f2(x) = O(g2(x)), то

(f1 · f2)(x) = O(g1(x) · g2(x)) .

Пример. Оцените сложность f(n) = 3n · log(n!).

Шаг 1. Из предыдущего примера log(n!) — это O(n · log(n)) .

Шаг 2. Пусть f1 = 3n и f2 = log(n!). Причем f = f1 · f2 .

Шаг 3. Обратите внимание. Что 3n = O(n).

Шаг 4. Из закона мультипликативной комбинации оценок сложности (как показано в теореме 3 выше) следует, что

g1(x) · g2(x) = O(n) · O(n · n log(n)) = O(n2 · log(n)) .

1.4.3. Обозначения Биг-Омега и Биг-Тета.

Обозначение Big-Oh устанавливает верхнюю границу сложности алгоритма. Поскольку | f(x) | C · | g(x) | для x больше некоторой константы k . Заданной константой C. (Знак меньше или равно обозначает. Что Big-Oh описывает верхнюю границу).

Чтобы установить нижнюю границу сложности. Мы используем обозначения (называемые Big-Omega) и (называемые Big-Theta).

Определение. Если f,g : RR-функции и C,k R+ такие, что

| f(x) | C · | g(x) | ,

тогда f(x) называется (g

Пример. Если f(x) = 8x3 + 5x2 + 7, то f(x) равно (x3), так как f(x) 8x3 x R+ .

Определение. Если ф,г : рр являются функциями. Где (А) Ф(Х) О(Г(х)) и (б) ф(х) (г(х)), то Ф(Х) называется (г(х)). Или Биг-тета — г(х) .

Примечание: Когда используется большая тета-нотация, то g(x) обычно является простой функцией (например. Nm, log n).

1.5. Рекурсивные вычисления

Часто полезно писать функции. Процедуры или методы. Которые вызывают себя. Этот метод. Называемый рекурсией, широко используется в информатике. Особенно при решении задач. Связанных с графами или деревьями. В этом разделе мы обсудим влияние рекурсивных процедур на вычислительные затраты с примерами.

Понятие. Рекурсивная процедура вызывает саму себя. Таким образом. В последовательности из n вызовов процедур выход n-й процедуры становится входом (n-1)-й процедуры. Которая становится входом (n-2)-й процедуры. И так далее. Пока не будет достигнута процедура верхнего уровня. Эта процедура обрабатывает выходные данные 2-го вызова процедуры в рекурсивной последовательности и возвращает чистый результат.

Пусть функция f(x) вычисляет выражение:

fi(x) = fi-1(x) + x , i = 1..n .

который просто вычисляет x + x + … + x столько раз. Сколько существует значений в i (в данном примере n раз).

Наблюдение. Если процедура. Для которой требуется вычислительная работа W (за исключением накладных расходов на вызов функции). Вызывает себя n раз. То эта процедура несет стоимость операций nW. Плюс дополнительные накладные расходы n-1 вызовов функций. Примечание: Первый вызов функции будет происходить независимо от того. Была ли процедура итеративной или вызывалась рекурсивно.

Замечание. Накладные расходы на дополнительные вызовы функций являются одним из существенных недостатков рекурсивного программирования. Дополнительным недостатком является сложность написания рекурсивной версии итерационной процедуры. Показателен следующий пример.

Рассмотрим следующие два фрагмента кода. Каждый из которых вычисляет x-факториал. Где x-положительное целое число:

НЕРЕКУРСИВНЫЙ РЕКУРСИВНЫЙ факториал(x : int) факториал(x : int): { fact = 1 { return(x * factorial(x-1)) 

Заметим. Что нерекурсивный или итеративный алгоритм более многословен. Чем рекурсивная формулировка. Оба вычисляют x!. И оба требуют для этого n-1 умножения. Однако нерекурсивный алгоритм имеет накладные расходы в виде приращений индекса цикла n-1, в то время как рекурсивный алгоритм требует n-1 дополнительных вызовов функций. Как обсуждалось ранее.

Рассмотрим следующие два фрагмента кода. Каждый из которых вычисляет сумму последовательности a из n элементов.

НЕРЕКУРСИВНЫЙ РЕКУРСИВНЫЙ sum(a : array [1..n] of int) sum(a : array [1..n] of int. I,n : int) { sum = 0 { if i = 1 for i = 1 to n then return(a[1]) 

Как и прежде. Обратите внимание. Что нерекурсивный или итеративный алгоритм имеет больше строк кода. Чем рекурсивная формулировка. Оба вычисляют сумму(a), и оба требуют для этого n-1 дополнений. Однако нерекурсивный алгоритм имеет накладные расходы в виде приращений индекса цикла n-1, в то время как рекурсивный алгоритм требует 2(n-1) приращений индекса i вместе с n-1 дополнительными вызовами функций. Как обсуждалось ранее. Это означает. Что рекурсивный алгоритм , вероятно. Не был бы лучшим способом вычисления векторной суммы.

Наблюдение. В большинстве вычислительных систем накладные расходы на вызовы функций намного превышают затраты на увеличение индекса цикла. Таким образом. Рекурсивная формулировка обычно (но не всегда) дороже. На практике нерекурсивная процедура является более дорогостоящей. Если вычисление индекса i или какого-либо другого индекса. Производного от i. Требует большого количества арифметических операций. Которые в совокупности были бы более дорогостоящими. Чем дополнительные вызовы функций рекурсивного вычисления. Тем не менее. Рекурсивная формулировка имеет то преимущество. Что она лаконична и способна изобразить вид вызовов функций. Которые математики часто любят писать с гораздо меньшими усилиями. Чем итеративные формулировки одной и той же функции.

Следовательно. Рекурсивные функции, вероятно. Останутся полезными в течение некоторого времени в будущем. Приложения рекурсивных вызовов функций изобилуют, например. В компиляторах. Синтаксическом анализе текста на формальном и естественном языках. А также в алгоритмах. Основанных на структурах данных. Называемых графами или деревьями.

1.6. Массивы и списки.

Начнем с нескольких наблюдений об использовании массивов в компьютерных программах.

Наблюдение. В первые дни компьютерного программирования машины были посвящены задаче вычисления таблиц траекторий артиллерии (Вторая мировая война) и таблиц учета и инвентаризации деловой информации (начало 1950-х годов). Таким образом. Для обработки линейных или двумерных массивов были разработаны вычислительные машины с интенсивной числовой нагрузкой. Когда компьютерное программирование стало более совершенным и научные приложения вошли в моду. Был разработан язык FORTRAN (FORmula TRANslation). Который поддерживал многомерные массивы.

Определение. Массив-это структура данных. Домен которой является конечным подмножеством евклидова n-пространства rn.

Наблюдение. Массивам обычно присваивается тип данных элементов. Которые они содержат. Который может быть одним и только одним типом данных. Например. Массивы могут быть целочисленными. Вещественными. Строковыми или символьными. Но элементы более чем одного такого типа обычно не содержатся в массиве.

Пример. Вектор a = (2,3,-1,5,6,0,9,-7) представляет собой одномерный целочисленный массив. Первое значение, обозначаемое a(1), равно 2. I-е значение в массиве обозначается a(i), i = 1..8, так как в массиве восемь элементов.

Пример. Двумерный массив, показанный ниже. Имеет четыре столбца и три строки. На каждый элемент массива ссылается его координата (строка,столбец). Например, элемент, значение которого равно 9.2, находится в строке 3, столбец 4, который мы записываем как (3,4) = 9.2 .


Рис. 1.6.1. Пример двумерного массива.

Замечание. Использование индексов строк-столбцов или координат делает ссылки на элементы массивов удобными. Особенно полезно отметить. Что массивы могут индексироваться в циклах. Например, цикл. Который установит все элементы массива a на рис. 1.6.1 равными нулю. Может быть записан в псевдокоде следующим образом::

 : DECLARE a : array [3,4] of real; : ДЛЯ i = от 1 до 3 СДЕЛАЙТЕ: ДЛЯ j = 1 - 4 DO: a(i,j) := 0,0 ENDFOR ENDFOR 

Наблюдение. В приведенном выше фрагменте псевдокода каждое измерение массива а имеет нижний и верхний пределы допустимых индексов. Размер каждого измерения определяется путем вычитания нижнего предела из верхнего. А затем прибавления единицы.

Пример. Если массив имеет размерность:

 b : массив [-2..3,5..9,4..8] целых чисел; 

затем количество элементов в массиве вычисляется следующим образом:

 ШАГ 1: Размер №1 имеет размер (3 - -2 + 1) = 6 ШАГ 2: Размер №2 имеет размер (9 - 5 + 1) = 5 ШАГ 3: Размер №3 имеет размер (8 - 4 + 1) = 5 ШАГ 4: Умножьте размеры измерений: Nэлементов = 6 x 5 x 5 = 150 

чтобы найти. Что в массиве есть 150 элементов.

В первые дни вычислительной техники было очень важно знать. Насколько велики массивы. Потому что компьютерная память была чрезвычайно ограничена. Сегодня, с большими моделями памяти. Все еще нужно быть осторожным. Чтобы не указать размеры массива слишком большими. Но это меньше проблемы. Чем в прошлом.

Подсказка по программированию: Как мы уже упоминали в классе. Всегда инициализируются программные переменные. Которым файловые данные не назначаются до вычисления данного выражения. Можно использовать предыдущую структуру цикла для эффективного назначения начальных значений элементам массива.

Ключевая проблема с массивами заключается в том. Что они имеют фиксированный размер. Поэтому их называют статическими структурами данных. Вскоре мы рассмотрим методы программирования структур данных . Называемых списками, которые могут расширяться и сжиматься с данными. Которые человек помещает в список или извлекает из него. Еще одна проблема массивов. О которой мы упоминали ранее. Заключается в том. Что они статически типизированы, т. е. не могут использоваться для хранения какого-либо типа данных. А только типа данных. Присвоенных им в операторе объявления. В котором они были указаны. Интересно отметить. Что некоторые языки. Такие как SNOBOL и ICON. Обошли эту трудность. Предоставив табличную структуру данных. Которая может содержать данные любого типа. Однако вы не несете ответственности за знание структуры данных ТАБЛИЦЫ. Поскольку она недоступна в Java или в большинстве современных языков программирования высокого уровня.

Далее мы рассмотрим случай односвязных и двусвязных линейных списков.

Мы видели, что массивы используют индекс для указания на каждый элемент массива. Например, если задан элемент массива a[i]. I = 1..n, то третий элемент массива, обозначаемый 3, будет указан как a[3]. Если n = 3 или больше. Другим типом линейной структуры данных. Сходной по концепции. Но не по реализации с одномерным массивом. Является список.

Определение. Список-это упорядоченная коллекция элементов. Где каждый элемент имеет по крайней мере один указатель и по крайней мере одно значение.

Определение. Односвязный список (SLL) — это список. В котором каждый элемент имеет следующие поля:

Значение: Значение, которое хранится в элементе списка. Это может быть любой тип данных. Включая список. Таким образом. Списки могут быть многомерными. То есть элемент списка может указывать на другой список через свое поле значений.

Next-pointer: Это указатель на следующий элемент в списке. Если он существует и имеет тип данных list-element.

Соглашение. Учитывая элемент SLL. Называемый this, мы обычно ссылаемся на значение элемента и следующий указатель как this.value и this.nextсоответственно.

Наблюдение. Как показано на схематической схеме SLL на рис. 1.6.2, существуют различные способы построения представлений списков. Показаны два — верхний пример имеет sentinel головные и хвостовые узлы. Которые представляют собой дополнительные затраты на хранение и обслуживание. Но могут обеспечить определенную степень безопасности данных. Если используются операции управления головными и хвостовыми узлами. Упрощенное представление списка. Без головных или хвостовых узлов sentinel. Более распространено. В этом случае первый узел-это голова. А последний узел (тот. Который указывает на нулевое значение) — это хвост списка.


Рис. 1.6.2. Принципиальная схема Односвязного списка. Где L[i], i=1..n. Обозначает значение в i-м элементе списка.

Определение. Двусвязный список (DLL)-это список. В котором каждый элемент имеет следующие поля:

Значение: Значение, которое хранится в элементе списка. Это может быть любой тип данных. Включая список. Таким образом. Списки могут быть многомерными. То есть элемент списка может указывать на другой список через свое поле значений.

Next-pointer: Это указатель на следующий элемент в списке. Если он существует и имеет тип данных list-element.

Prev-pointer: Это указатель на предыдущий элемент в списке. Если он существует и имеет тип данных list-element.

Соглашение. Учитывая элемент DLL. Называемый this, мы обычно ссылаемся на значение элемента. Next-pointer и prev-pointer как this.value, this.nextи this.prevсоответственно.

Наблюдение. Найти головку и хвост библиотеки DLL немного проще. Чем с SLL. Так как prev-указатель (next-указатель) головки (хвоста) библиотеки DLL указывает на нулевое значение.


Рис. 1.6.3. Принципиальная схема Двусвязного списка. Где L[i], i=1..n. Обозначает значение в i-м элементе списка.

Наблюдение. Обход библиотеки DLL проще. Чем обход SLL. Потому что prev-указатель библиотеки DLL позволяет вернуться назад (т. Е. Пройти список назад). Это важно в некоторых типах операций сортировки или поиска. Выполняемых над списками. SLL имеют то преимущество. Что они немного проще. Чем библиотеки DLL. И их легче реализовать. Поскольку они имеют 2/3 полей данных библиотеки DLL.

Операции ADT. SLL или DLL имеет следующие операции ADT:

Size(): Возвращает количество элементов в списке.

isEmpty(): Возвращает true, если в списке нет элементов.

i-th(i): Возвращает значение i-го элемента в списке. Эта функция иногда называется ElementAt(i).

Head(): Возвращает значение первого элемента в списке.

Tail(): Возвращает значение последнего элемента в списке.

Insert(x,i): Вставляет новый элемент в список после i-го элемента. Где новый элемент имеет значение x. Каждый из (i+1)-го и последующих элементов имеет свои индексы. Увеличенные. То есть (i+1)-й элемент становится (i+2)-м элементом и так далее.

Delete(i): Удаляет i-й элемент из списка. (i+1)-й и последующие элементы имеют свои индексы. Уменьшенные. То есть (i+1)-й элемент становится i-м элементом. И так далее.

Наблюдение. Операция i-го или ElementAt несет O(n) сложность для n-элементного SLL или DLL. Таким образом. Если вы помещаете операцию ElementAt в цикл. Имеющий m итераций. Это повлечет за собой требование работы O(n2) операций.


Рис. 1.6.4. Принципиальная схема вставки элемента со значением Обратите внимание. Что шаги 1-3 обобщают вставку в SLL. Если и только если узлы списка являются узлами SLL. Как показано на рис. 1.6.2.


Рис. 1.6.5. Результат операции вставки в DLL. Шаги на рис. 1.6.4 пронумерованы синим цветом.

Сложность. Работа по вставке элемента в библиотеку DLL, как показано на рис. 1.6.4, представляет собой (а) создание одного элемента списка плюс (б) четыре назначения указателей списка. Для SLL эта работа сводится к двум назначениям указателя. Так как указатель prev-элемента не доступен для использования в SLL. Предыдущая оценка работы не включает в себя работу. Необходимую для поиска списка.

1.7. Поиск, Отбор и сортировка

В информатике нам часто приходится выполнять практические задачи. Такие как поиск записи в таблице или словаре. Поиск элементов в базе данных и т. Д. Процесс поиска таких элементов также называется отбором, поскольку каждый пытается выбрать заданное значение из массива, списка. Набора или другого ADT. Выбор обсуждается в разделе 1.7.1.

Другой важной задачей в информатике является упорядочение списка имен. Чисел или других данных в соответствии с заранее определенной схемой упорядочения. Этот процесс. Называемый сортировкой. Был широко исследован и стал предметом многих исследований в 1950-х-1970-х годах. Таким образом. Существует множество алгоритмов сортировки. Представляющих интерес. Некоторые из них мы рассмотрим в разделе 1.7.2.

1.7.1. Выбор

В этом вводном классе есть два типа алгоритмов отбора. Представляющих интерес. Во-первых, у нас есть простой метод линейного поиска, который просто сканирует каждый элемент структуры данных. Чтобы увидеть. Соответствует ли его значение заранее заданному или эталонному значению. Это требует O(n) работы для поиска по n данным. Во-вторых, можно создавать иерархические структуры данных. Называемые деревьями, для которых существуют алгоритмы поиска. Которые могут найти данные в O(log n) работе.

Линейный поиск сканирует список. Массив или другой ADT. Сравнивая значение каждого элемента с эталонным значением. При первом совпадении алгоритм поиска возвращает позицию интересующего значения.

Анализ. Наилучший вариант для алгоритма линейного поиска-иметь значение x. Для которого выполняется поиск. Расположенное в первой позиции АЦП. Это, очевидно. Требует постоянного числа операций сравнения. То есть работы сравнения O(1). В худшем случае x находится в n-й позиции АДТ. Для которой соответствующая работа равна O(n).

При заданном n-элементном векторе aлинейный поиск элемента x может быть реализован следующим образом:

LinSearch(x,a,n): 

Анализ. Предыдущий алгоритм берет на себя минимум (максимум) 1 (n) сравнений при среднем требовании работы (n+1)/2 сравнений.

Пример. Учитывая пятиэлементный вектор a = (2,8,32,7,4). Давайте искать элемент a[i] = 7, i = 1..5. Следующая таблица достаточна для примера линейного поиска:

 ШАГ i ЗНАЧЕНИЕ a[i] ПРОВЕРКА РЕЗУЛЬТАТА СЛЕДУЮЩИЙ i ---- ------- ---- --------- -------- -------- 1 1 2 а[1] = 7? 2!= 7 2 2 2 8 а[2] = 7? 8!= 7 3 3 3 32 a[3] = 7? 32!= 7 3 4 4 7 a[2] = 7? 7 = 7 стоп 

Наблюдение. Деревья поиска обычно являются двоичными. То есть на каждый внутренний узел приходится по два дочерних элемента. Это позволяет использовать двоичное отношение типа больше-чем или меньше-чем для построения min-дерева или max-дерева, которое имеет в корне дерева минимум или максимум данных. Хранящихся в дереве. Мы излагаем более общий случай следующим образом.

Определение. N-арное дерево поиска-это корневое дерево. Имеющее n дочерних элементов на каждый нетерминальный узел.

Определение. В n-арном дереве поиска уровней глубины L требуется O (L) операций для поиска заранее заданного значения. Хранящегося в одном из узлов дерева. Учитывая m элементов данных. Хранящихся в полном n-арном дереве поиска. Число уровней вычисляется следующим образом:

L = ceil(lognm) ,

где ceil обозначает потолочную функцию.

Наблюдение. Недостатком некоторых типов деревьев поиска. Таких как бинарные деревья поиска. Является то. Что последовательность. Хранящаяся в дереве. Должна быть предварительно отсортирована. Чтобы иметь свойство order. Необходимое для реализации работы O(log n) в процессе выбора. Однако другие типы деревьев поиска. Такие как некоторые реализации бинарных деревьев поиска, AVL-деревьев и красно-черных деревьев, рассмотренные в разделе 3, требуют только O(log n) работы для вставки и удаления элемента из дерева.

1.7.2. Сортировка

Существует несколько типов алгоритмов сортировки. Представляющих интерес для данного курса. Во-первых, у нас есть простая техника инъекционной сортировки, которая помещает каждое входное значение в его позицию в числовой строке. Используя это значение в качестве индекса для отсортированного массива. Более сложный метод сортировки. Называемый сортировкой по гистограммам или бин-сортировкой, сканирует гистограмму последовательности и выводит значения. Хранящиеся в гистограмме. В заданном порядке. Поскольку предполагается. Что область гистограммы представляет собой n-элементное подмножество целых или вещественных чисел. То требуется O(n) сложений и операций ввода-вывода.

Более сложные алгоритмы сортировки были разработаны для обработки больших входных последовательностей. Которые имели произвольные значения. Например, пузырьковая сортировка переносит максимум или минимум последовательности в начало последовательности. Оставшаяся часть последовательности затем сортируется таким же образом. Это означает. Что есть n проходов. Где i-й проход требует сканирования через i данные. Это включает в себя O(n2) сравнение и операции ввода-вывода и. Таким образом. Является запретительным для очень больших последовательностей. Более интеллектуальная (и эффективная) техника вставки-сортировка выборочно помещает каждое значение входной последовательности в соответствующее положение в последовательности в соответствии с заранее определенным порядком. Это можно рассматривать как тип интеллектуального алгоритма пузырьковой сортировки и требует гораздо меньше операций. Чем пузырьковая сортировка.

Еще более эффективные алгоритмы сортировки включают сортировку слиянием и быструю сортировку, которые имеют древовидную структуру. Эти алгоритмы. Которые относятся к общему классу разделяй и властвуй алгоритмы. Сначала разбивают (делят) входную последовательность на подпоследовательности. Которые затем сортируются. Когда данная подпоследовательность имеет два элемента. (Обратите внимание. Что последовательности. Имеющие один элемент. Не нуждаются в сортировке.) Затем подпоследовательности рекомбинируются. Чтобы получить отсортированную последовательность. Сортировка слиянием разбивает входную последовательность на основе ее длины. Которая считается степенью двойки. Поскольку используется двоичное дерево. Быстрая сортировка разбивает входную последовательность на основе сводного значения, вычисляемого из значений в последовательности. Поэтому говорят. Что быстрая сортировка зависит от данных.

1.7.1.1. Сортировка Инъекций.

Концепция. Учитывая входную последовательность [an], которая является подмножеством целых чисел по модулю n. Инъекционная сортировка помещает каждое значение a(i) в соответствующее место в числовой строке.


Рис. 1.7.1. Принципиальная схема инжекционной сортировки. Применяемой к входному вектору (2,4,3,1) для получения отсортированного вектора (1,2,3,4).

Предположим . Что последовательность a имеет n различных целых чисел. Взятых из множества Zn, где n мало (то есть меньше 1 М). Мы можем отсортировать а следующим образом:

InjectionSort(a : массив [1..n] целого числа по модулю n): { для i = 1 - n do: 

Анализ. Предыдущий алгоритм состоит из одного цикла. Который имеет n итераций и выполняет работу двух операций ввода-вывода памяти во время каждой итерации. Таким образом. Общая работа составляет 2n операций ввода-вывода памяти. А алгоритм сортировки инъекций сортирует свои входные данные с помощью O(n) работы.

Инъекционная сортировка не имеет наилучшего или наихудшего входа. Потому что один и тот же процесс применяется к каждому входу. Независимо от того. Как он упорядочен. Другой способ сказать это-заметить. Что в алгоритме нет операторов принятия решений и. Следовательно. Нет способа выйти из цикла до завершения. Мы говорим. Что такой алгоритм имеет производительность или сложность. Которые не зависят от данных.

1.7.1.2. Сортировка гистограмм (Bin Sort).

Концепция. Учитывая входную последовательность [an], значения которой могут быть сопоставлены целым числам по модулю m. Где m > n возможно. Гистограммная сортировка (также называемая > bin-сортировкой) помещает каждое значение a(i) в соответствующее место на числовой строке путем сканирования гистограммы a.


Рис. 1.7.2. Принципиальная схема сортировки гистограммы. Примененной к входному вектору (2,1,4,2,3,1,4,1) для получения отсортированного вектора (1,1,1,2,2,3,4,4).

Предположим . Что последовательность a имеет n различных элементов. Которые могут быть сопоставлены множеству Zm, где m мало. Мы можем отсортировать a, используя его гистограмму h(a), следующим образом:

HistogramSort(a : массив [1..n] целого числа по модулю n): { h = 0 # Обнулить буфер гистограммы для i = 1 - n do: # Построить гистограмму 

Анализ. Предыдущий алгоритм состоит из двух циклов. Первый цикл имеет n итераций и выполняет работу одной операции ввода-вывода памяти и одного приращения во время каждой итерации. Второй цикл-это сложный цикл (j и k- индексы). Который повторяется в общей сложности n раз. Так как в гистограмме есть n данных (напомним. Что было n входных данных). Для каждой итерации второго цикла существует одно приращение (i++) и одна операция ввода-вывода памяти. Таким образом. Общая работа составляет 2n операций ввода-вывода памяти и приращений. А алгоритм сортировки гистограммы сортирует свой вход с помощью O(n) работы.

По тем же причинам. Что и в разделе 1.7.1.1 Однако. Как и сортировка инъекций. Сортировка гистограмм требует очень ограниченного ввода. Что не обязательно является реалистичным ограничением.

Поскольку говорят, что гистограмма состоит из ячеек, в которых хранится счетчик для данного значения (например. Помещая n бобов в ячейку x. Если значение x встречается n раз). Сортировку гистограммы часто называют сортировкой по ячейкам.

Далее мы переходим от алгоритмов сортировки сложности O (n) с ограниченными входными наборами к раннему алгоритму сортировки с неограниченными реальными входными значениями.

1.7.1.3. Сортировка пузырьков.

Концепция. Учитывая входную последовательность [an], значения которой считаются действительными числами. Пузырьковая сортировка помещает каждое значение a(i) на свое надлежащее место в числовой строке. Соответственно «пузырясь» или перенося минимум (максимум) последовательности или оставшуюся подпоследовательность для достижения сортировки в восходящем (нисходящем) порядке.


Рис. 1.7.3. Принципиальная схема пузырьковой сортировки. Примененной к входному вектору (2,1,4,2,3) для получения отсортированного вектора (1,2,2,3,4). Обратите внимание. Что ограниченные области-это области. К которым применяется пузырьковая сортировка. Каждая из этих областей уменьшается на один элемент и равна по размеру n-i. Где i обозначает индекс шага обработки.

Предположим. Что последовательность a имеет n вещественных элементов. Которые не обязательно должны быть различны. Мы можем отсортировать a в порядке возрастания с помощью пузырьковой сортировки следующим образом:

BubbleSort(a,n): { read(a[i]. I = 1..n) for i = 1 to n do: min = минимум последовательности a[i..n] pos = позиция. В которой произошел минимум b[i] = min swap(a[i],a[pos]) 

Анализ. Предыдущий алгоритм состоит из одного цикла. Который имеет n итераций и выполняет работу (n-i+1) сравнения на итерацию. Таким образом. Сложность равна O(n) сравнения. Которые доминируют над операциями ввода-вывода памяти.

В лучшем случае входные данные предварительно сортируются. А пузырьковая сортировка требует минимального количества операций ввода-вывода. (Подсказка: Точное количество операций ввода-вывода может быть хорошим экзаменационным вопросом.)

В худшем случае входные данные сортируются в противоположном от желаемого порядка отсортированных выходных данных порядке. И требуется максимальное количество операций ввода-вывода. Число сравнений инвариантно к входному значению. Так как максимум каждой последовательности или подпоследовательности априори не известен.

1.7.1.4. Сортировка вставки.

Концепция. Учитывая входную последовательность [an], значения которой считаются числами. Вставка-сортировка помещает каждое значение a(i) на свое надлежащее место в отсортированной последовательности. «пузырясь» или перенося минимум (максимум) последовательности или оставшуюся подпоследовательность. Только если это значение не в порядке.


Рис. 1.7.4. Принципиальная схема сортировки вставки. Применяемой к входному вектору (2,1,4,2,3) для получения отсортированного вектора (1,2,2,3,4). Обратите внимание. Что данный обмен завершается определением порядка InPlace. Независимо от того. Сколько шагов находится в обмене. Кроме того, когда маркер находится в конечной позиции (в данном случае в пятой позиции. Потому что n = 5). Это сигнализирует об окончательном обмене.

Предположим. Что последовательность a имеет n элементов. Которые не должны быть различны. Мы можем сортировать a в порядке возрастания. Используя insert-sort. Следующим образом:

InsertionSort(a,n): 

Анализ. Предыдущий алгоритм состоит из одного цикла. Который имеет n итераций и выполняет максимум O(n) сравнений за итерацию. Это происходит. Когда входная последовательность сортируется в порядке. Противоположном желаемому выходу (наихудший случай). В лучшем случае входная последовательность правильно сортируется. И требуется в общей сложности n-1 сравнений (потому что предыдущая подпоследовательность уже отсортирована). Таким образом. Сложность сортировки вставки варьируется от O(n) до O(n2) сравнения. Которые доминируют над операциями ввода-вывода памяти. По этой причине алгоритм InsertionSort имеет сложность. Зависящую от данных.

1.7.1.5. Сортировка слиянием.

Понятие. Заданная входная последовательность [an], значения которых считаются числами. А n-степенью 2 для удобства. Merge-sort использует divide-and-conquer для рекурсивной сортировки входных данных до тех пор. Пока не появятся подпоследовательности только из двух элементов. Они сортируются с помощью одного сравнения и одной операции подкачки (если требуется). А затем объединяются в постепенно увеличивающиеся подпоследовательности. Пока не будет достигнута входная длина. В результате получается упорядоченная последовательность. Как показано на рис. 1.7.5, алгоритм MergeSort состоит из (1) шагов разделения. (2) сортировки и (3) слияния. Для целей для ясности мы предполагаем. Что входные данные MergeSort состоят из различных целых чисел.


Рис. 1.7.5. Принципиальная схема сортировки слиянием. Применяемая к входному вектору (2,8,5,3,7,1,6,4) для получения отсортированного вектора (1,2,3,4,5,6,7,8).

Предположим. Что последовательность a имеет n элементов. Которые не должны быть различны. Мы можем отсортировать a в порядке возрастания с помощью merge-sort следующим образом:

Слияние(L1,L2): { L3 = пустой список повторяйте до тех пор. Пока список L1 или список L2 не станет пустым: если головка(L1) )) иначе вставить головку(L2) в головку L3 удалить(head(L2)) MergeSort(a,n): { если size(a) = 1, то return(a) elseif size(a) = 2, то если a[1] и a[2] не находятся в правильном порядке. То swap(a[1],a[2]) endif else { разделите a на два списка одинакового размера. L и R 

Пример слияния. Работа алгоритма слияния может быть интуитивно не очевидна. Поэтому мы приведем следующий пример. В котором две 2-элементные сортированные последовательности из Рисунок 1.7.5 объединены.

Таким образом. Можно видеть. Что слияние в порядке возрастания (убывания) — это просто вопрос вывода меньшего (большего) из глав списка. А затем удаления этого элемента из соответствующего списка. Поскольку списки L1 и L2 уже отсортированы. Это возможно. Если бы L1 и L2 не были в порядке. Слияние не сработало бы.

Другой способ думать о слиянии-это представить себе процесс. При котором две колоды из n карт. Каждая из которых отсортирована. Могут быть перетасованы. Чтобы получить одну отсортированную колоду.

Анализ. Предыдущий алгоритм MergeSort вызывает себя рекурсивно log(n)-1 раз. Это приводит к построению рекурсивного дерева уровней log(n). Операция подкачки добавляет еще один уровень к дереву. А результирующие операции слияния разматывают стек рекурсии. Чтобы получить еще один уровень журнала(n).

  • Фаза расщепления (divide) требует всего лишь (n/2 + 1) битовых операций. Если используется реализация массива. В противном случае на каждом уровне требуется n операций ввода-вывода. В общей сложности O(n log(n)) операций.

  • Этап сортировки требует n/2 сравнений и максимум n операций ввода-вывода. Если каждая 2-элементная подпоследовательность несортирована.

  • Фаза слияния разматывает стек рекурсии и требует m-1 сравнений для каждого набора из двух m-элементных подпоследовательностей. Поскольку в части слияния архитектуры сортировки есть уровни O (log n). А m является функцией n. Требуется в общей сложности O(n log(n)) операций сравнения.

  • Это означает. Что алгоритм сортировки слиянием требует работы O(n log(n)). С точки зрения сравнения. Нет ни лучшего. Ни худшего случая. Однако накладные расходы на ввод-вывод уменьшаются. Когда каждая 2-элементная подпоследовательность. Встречающаяся на уровне сортировки. Сама сортируется.

    Аналогично, поскольку алгоритм слияния проверяет порядок каждого элемента в последовательностях. Подлежащих слиянию. Нет лучшего или худшего случая. Таким образом. MergeSort не зависит от данных с точки зрения операций сравнения. Но зависит от данных с точки зрения операций ввода-вывода.

    1.7.1.6. Быстрая сортировка.

    Быстрая сортировка концептуально похожа на сортировку слиянием. Но может немного улучшить производительность сортировки слиянием. Исключив фазу слияния. Это имеет место в основном тогда. Когда входные данные могут быть разделены таким же образом. Как входные данные merge-sort (т. Е. Деление пополам каждой последовательности или подпоследовательности на каждом уровне дерева).

    Учитывая входную последовательность [an], значения которой считаются числами. А n произвольно. Quick-sort использует метод Они сортируются с помощью одного сравнения и одной операции подкачки (если требуется). А затем объединяются в постепенно увеличивающиеся подпоследовательности. Пока не будет достигнута входная длина. В результате получается упорядоченная последовательность. Разница между сортировкой слиянием и быстрой сортировкой заключается в том. Что быстрая сортировка использует сводное значение вместо размера последовательности или подпоследовательности нужно решить. Как разбить входные данные.


    Рис. 1.7.6. Принципиальная схема быстрой сортировки. Применяемая к входному вектору (42,43,2,1,46,4,45) для получения отсортированного вектора (1,2,4,42,43,45,46).

    Предположим. Что последовательность a имеет n элементов. Которые не должны быть различны. Мы можем отсортировать a в порядке возрастания с помощью быстрой сортировки следующим образом:

    QuickSort(a): { если size(a) = 1, то return(a) elseif size(a) = 2, то если a[1] и a[2] не в правильном порядке. То swap(a[1],a[2]) endif else { pick a pivot value p based on the values of a split a into two lists, L and R. Where { L содержит значения a. Которые меньше p 

    Анализ. Предыдущий алгоритм рекурсивно называет себя минимум ceil(log(n))-1 раз и максимум n-1 раз (наихудший случай). Это приводит к построению дерева рекурсии. Имеющего log(n)-n-1 уровни. Операция подкачки добавляет еще один уровень к дереву. А результирующие операции конкатенации раскручивают стек рекурсии . Чтобы получить еще один журнал(n) до n уровней.

  • Фаза расщепления (divide) требует уровней log(n) в лучшем случае. Если медиана каждой последовательности или подпоследовательности выбрана в качестве опорного значения. Другие схемы разворота рискуют разбить входные данные на части. Отличные от их позиционной средней точки.

  • Фаза сортировки требует n/2 сравнений и максимум n операций ввода-вывода. Если в результате получаются 2-элементные подпоследовательности (лучший случай) и каждая 2-элементная подпоследовательность несортирована.
  • Фаза конкатенации разматывает стек рекурсии и не требует никаких сравнений. В отличие от сортировки слиянием. Поскольку в конкатенационной части архитектуры сортировки есть уровни log(n)-n-1 и каждый уровень имеет n операций ввода-вывода. Требуется в общей сложности от O(n log(n)) до O(n2) операций ввода-вывода.
  • Это означает. Что алгоритм быстрой сортировки требует работы от O(n log(n)) до O(n2), в зависимости от того. Как выбрано значение pivot. Если медиана выбрана в качестве опорной точки. То быстрая сортировка может быть немного быстрее. Чем сортировка слиянием. Поскольку в фазе завоевания нет сравнений.

    Наилучший вход-это последовательность. Которая имеет все подпоследовательности. Полученные путем расщепления с тем же средним значением. Что и их медиана. Так как это дает наименьшее количество уровней. Наихудшим входом для разбиения на среднее значение является геометрический ряд. Отсортированный в порядке. Противоположном желаемому порядку сортировки. Например (10,100,1000,…). Когда берется среднее значение. Такая последовательность потребует n-1 уровней расщепления и n-1 уровней конкатенации. Потому что она будет разбита на n-2 подпоследовательности по одному элементу каждая и одну подпоследовательность из двух элементов.

    Примечание: Учащиеся должны проверить это. Построив диаграмму расщепления и конкатенации для последовательности S = (101,102,…,108).

    В разделе 2 мы рассмотрим структуры данных. Такие как наборы и строки. Которые могут быть представлены списками. А затем рассмотрим специальную структуру данных. Называемую кучей. Будет показано. Что алгоритм сортировки. Основанный на куче (неудивительно. Что он называется HeapSort), может достичь сложности O(n log(n)) и его легче реализовать. Чем MergeSort.