- •Структуры и алгоритмы обработки данных
- •Логическая и физическая структуры данных
- •Классификация структур данных
- •Основные операции над структурами данных
- •Алгоритм и примеры задач, решаемых с помощью алгоритмов
- •Адресация и распределение памяти
- •Адресные пространства и модели оперативной памяти
- •Формирование физического адреса в реальном режиме
- •Особенности адресации в защищенном режиме
- •Кэширование
- •Анализ алгоритмов
- •Быстродействие – основной показатель эффективности алгоритма
- •Подсчет числа простейших операций
- •Лучший, средний и худший случаи
- •Алгоритмы и платформы
- •Виртуализация памяти
- •Использование кэша
- •Выравнивание данных
- •Рандомизированные алгоритмы
- •Общая характеристика записей и способы описания в Delphi
- •Многоуровневые записи
- •Выравнивание и упакованные записи
- •Записи с вариантной частью
- •Массивы
- •Общая характеристика массивов
- •Статические (стандартные) массивы
- •Многомерные статические массивы
- •Свойства статических массивов
- •Открытые массивы
- •Динамические массивы
- •Динамические векторы
- •Многомерные динамические массивы
- •Массивы типа Variant
- •Вставка и удаление в массиве
- •Связные списки и алгоритмы их обработки
- •Списки и их разновидности
- •Односвязный список
- •Общая характеристика односвязного списка
- •Структура элемента односвязного списка
- •Формирование односвязного списка
- •Просмотр односвязного списка
- •Вставка элемента в односвязный список
- •Удаление элемента из односвязного списка
- •Линейный двухсвязный список
- •Структура элемента двухсвязного списка
- •Реализация операций в линейном двухсвязном списке
- •Нелинейный двухсвязный список
- •Нелинейный трехсвязный список
- •Определение плекса и его общие признаки
- •Иерархическая списковая структура. Сетевая структура
- •Достоинства и недостатки связных списков
- •Функциональные и свободные списки
- •Общая характеристика функционального и свободного списка
- •Методы формирования свободного списка
- •Стеки, очереди, деки и операции в них
- •Общая характеристика
- •Очередь
- •Динамические множества и словари
- •Общая характеристика
- •Операции в динамических множествах
- •Деревья
- •Общая характеристика и некоторые определения
- •Представление дерева в памяти
- •Естественное представление дерева
- •Представление дерева с помощью вектора
- •Представление дерева с использованием списков сыновей
- •Методы обхода деревьев
- •Бинарное дерево
- •Структура бинарного дерева
- •Формирование бинарного дерева
- •Обход бинарного дерева
- •Преобразование любого дерева к бинарному дереву
- •Включение и исключение в дереве
- •Включение в дереве
- •Исключение в дереве
- •Поиск: определение и общая терминология
- •Линейный (последовательный) поиск
- •Последовательный поиск в упорядоченной таблице
- •Последовательный поиск при накоплении запросов
- •Индексно-последовательный поиск
- •Бинарный поиск
- •Поиск, использующий бинарное дерево
- •Сортировка
- •Общие сведения и некоторые определения
- •Внутренняя сортировка
- •Сортировка прямыми включениями
- •Сортировка бинарными включениями
- •Сортировка прямым выбором
- •Сортировка прямым обменом
- •Сортировка методом Шелла
- •Сортировка с помощью бинарного дерева
- •Пирамидальная сортировка
- •Быстрая сортировка разделением
- •Внешняя сортировка
- •Сортировка прямым слиянием
- •Сортировка естественным слиянием
- •Сортировка многопутевым слиянием
- •Многофазная сортировка
- •Хеширование и хеш-таблицы
- •Общие сведения и определения
- •Коллизии при хешировании
- •Разрешение коллизий при хешировании
- •Разрешение коллизий методом открытой адресации
- •Разрешение коллизий методом цепочек
- •Функции хеширования
- •Поисковые деревья
- •Бинарное дерево поиска
- •Структура бинарного дерева поиска и алгоритм поиска
- •Вставка элемента в бинарное дерево поиска
- •Удаление из бинарного дерева поиска
- •Красно-черные деревья
- •Определение красно-черного дерева, структура его элементов
- •Повороты
Подсчет числа простейших операций
В соответствии с методом подсчета простейших операций алгоритм представляется в виде программы на развитом языке программирования (например, Pascal). Определяется множество простейших операций высокого уровня, которые не зависят от языка программирования. К таким операциям относятся:
присваивание переменной значения,
вызов метода (процедуры или функции),
выполнение арифметической операции,
сравнение двух значений,
индексация массива,
переход по ссылке на объект,
возвращение из метода.
Данный метод основан на неявном предположении, что время выполнения простейших операций приблизительно одинаково. Таким образом, К простейших операций, выполняемых внутри алгоритма, пропорционально действительному времени выполнения данного алгоритма.
Рассмотрим процесс подсчета простейших операций на примере алгоритма определения максимального значения в одномерном массиве X, состоящего из N элементов. На рисунке 3.2 приводится код данного алгоритма на языке Pascal.
begin
currentMax:= X[0];
for i:= 1 to N-1 do
if currentMax < X[i] then currentMax:= X[i];
end;
Рисунок 3.2 – Pascal-код алгоритма определения максимального значения в массиве
Приведем рассуждения, формулируемые в процессе анализа:
на этапе инициализации переменной currentMax и присваивания ее значения X[0] выполняются две простейшие операции (индексация массива и присваивание значения); таким образом, счетчик операций равен 2;
в начале цикла for счетчик i получает значение 1, что соответствует одной простейшей операции присваивания;
перед выполнением тела цикла проверяется условие i< N (операция сравнения); такое сравнение выполняется N раз, поэтому счетчик простейших операций увеличивается еще на N единиц;
тело цикла выполняется для значений i, равных 1, 2, …, N-1. При каждой итерации X[i] сравнивается с currentMax (две простейших операции – индексирование и сравнение), значение X[currentMax], возможно, присваивается переменной currentMax (две операции – сложение и присваивание), а счетчик i увеличивается на 1 (две операции – сложение и присваивание). Следовательно, при каждой итерации цикла выполняется 4 или 6 простейших операций, в зависимости от выполнения одного из условий X[i] currentMax или X[i]> currentMax. Таким образом, при выполнении тела цикла в счетчик операций добавляется 4(N–1) или 6(N–1);
при возвращении значения переменной currentMax однократно выполняется одна простейшая операция.
Итак, число простейших операций К(N), выполняемых алгоритмом, минимально равно
,
а максимально
.
Число выполняемых простейших операций равно минимально (К(N) = 5N) в том случае, если X[0] является максимальным элементом массива, т. е. переменной currentMax не присваивается нового значения. Число выполняемых операций максимально равно 7N–2 в том случае, если элементы массива упорядочены по возрастанию, и переменной currentMax присваивается значение при каждой итерации цикла.
О-нотация
Для выражения характеристик быстродействия в вычислительной технике используется короткая схема – О-нотация (big-Oh notation). В этой нотации используется специальная математическая функция от N, т. е. количества исходных данных, которому пропорционально быстродействие алгоритма. Утверждается, что алгоритм принадлежит к классу О(f(N)), где f(N) – некоторая функция от N. Приведенное обозначение читается как «О большое от f(N)» или, менее строго, «пропорционально f(N)»
Например, исследования показали, что алгоритм А принадлежит к классу О(N), а алгоритм В – к классу О(log(N)). Поскольку для положительных чисел log(N) < N, можно сделать вывод о том, что алгоритм В всегда эффективнее алгоритма А.
О-нотация подчиняется простым арифметическим правилам. Во-первых, умножение математической функции внутри скобок в О-нотации на константу не оказывает никакого влияния на О-нотацию. Например, О(3f(N)) и О(24f(N)) эквивалентно О(f(N)), поскольку константы 3 или 24 можно без последствий вынести за скобки как коэффициент пропорциональности, который игнорируется.
Во-вторых, О-нотация демонстрирует асимптотическое поведение, проявляющееся в том, что для больших значений N О-нотация определяет тот класс алгоритма, к которому принадлежит его доминантная часть. Пусть некоторый алгоритм принадлежит к классу О(N2 + N). Если величина N достаточно велика, то влияние члена «+N» поглощается членом «N2». Другими словами при больших значениях N алгоритм О(N2 + N) эквивалентен алгоритму О(N2). То же можно сказать и для более высоких степеней N.
Предположим, что есть алгоритм, который выполняет три различных задачи. Первая задача выполняется алгоритмом класса О(N), вторая – алгоритмом класса О(N2), третья – алгоритмом класса О(log(N)). Каково будет быстродействие алгоритма в целом. Ответ будет О(N2), поскольку к этому классу принадлежит доминантная часть алгоритма.
Таким образом, значения О большого характеризуют алгоритм для больших значений N, а для маленьких значений N О-нотация не имеет смысла.