Основы дискретной математики

Вставляя узел, нам понадобится определить количество исходящих от него ссылок. Эта проблема легче всего решается с использованием случайного механизма: при добавлении нового узла мы «бросаем монету», чтобы определить, нужно ли добавлять еще слой. Например, мы можем добавлять очередные слои до тех пор, пока выпадает «решка». Если реализован только один уровень, мы имеем дело фактически с обычным

списком и время поиска есть O(n). Однако если имеется достаточное число уровней, разделенный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска есть O (lg n).

Поскольку реализация разделенных списков включает в себя случайный процесс, для времени поиска в них устанавливаются вероятностные границы. При обычных условиях эти границы довольно узки. Например, когда мы ищем элемент в списке из 1000 узлов, вероятность того, что время поиска окажется в 5 раз больше среднего, можно оценить как 1/ 1,000,000,000,000,000,000 (рисунок 1.7).

Рисунок 1.7 – Устройство разделенного списка

1.2.3 Оценки времени исполнения

Для оценки эффективности алгоритмов можно использовать разные подходы. Самый бесхитростный – просто запустить каждый алгоритм на нескольких задачах и сравнить время исполнения. Другой способ – оценить время исполнения. Например, мы можем утверждать, что время поиска есть O(n) (читается так: о большое от n). Это означает, что при больших n время поиска не сильно больше, чем количество элементов. Когда используют обозначение O(), имеют в виду не точное время исполнения, а только его предел сверху, причем с точностью до постоянного множителя. Когда говорят, например, что алгоритму требуется время порядка O(n2), имеют в виду, что время исполнения задачи растет не быстрее, чем квадрат количества элементов. Чтобы почувствовать, что это такое, посмотрите таблицу 1.1, где приведены числа, иллюстрирующие скорость роста для нескольких разных функций. Скорость роста O(log2n) характеризует алгоритмы типа двоичного поиска.

Таблица 1.1 – Скорость роста нескольких функций O()

Если считать, что числа в таблице 1.1 соответствуют микросекундам, то для задачи с 1048476 элементами алгоритму со временем работы O(log2 n) потребуется 20 микросекунд, алгоритму со временем работы O(n1.25) – порядка 33 секунд, алгоритму со временем работы O(n2) – более 12 дней. В нижеследующем тексте для каждого алгоритма приведены соответствующие O‑оценки. Более точные формулировки и доказательства можно найти в [12], [15].

Как мы видели, если массив отсортирован, то искать его элементы необходимо с помощью двоичного поиска. Однако не забудем, что массив должен быть отсортированным! В следующем разделе мы исследует разные способы сортировки массива. Оказывается, эта задача встречается достаточно часто и требует заметных вычислительных ресурсов, поэтому сортирующие алгоритмы исследованы вдоль и поперек, известны алгоритмы, эффективность которых достигла теоретического предела.

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

1.2.4 Сортировки

Сортировка вставками

Один из простейших способов отсортировать массив – сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта находится не на месте. Как среднее, так и худшее время для этого алгоритма – O(n2). Дальнейшую информацию можно получить в книге Кнута [4].

На рисунке 1.8 (a) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз – до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рисунке 1.8 (b) для числа 1. Наконец, на рисунке 1.8 (c) мы завершаем сортировку, поместив 2 на нужное место.

Рисунок 1.8 – Сортировка вставками

Если длина нашего массива равна n, нам нужно пройтись по n – 1 элементам. Каждый раз нам может понадобиться сдвинуть n – 1 других элементов. Вот почему этот метод требует довольно-таки много времени.

Сортировка вставками относится к числу методов сортировки по месту. Другими словами, ей не требуется вспомогательная память, мы сортируем элементы массива, используя только память, занимаемую самим массивом. Кроме того, она является устойчивой – если среди сортируемых ключей имеются одинаковые, после сортировки они остаются в исходном порядке.

Сортировка с помощью включения

Кто играл в карты, процедуру сортировки включениями осуществлял многократно. Как правило, после раздачи карт игрок, держа карты веером в руке, переставляет карты с места на место, стремясь их расположить по мастям и рангам, например, сначала все тузы, затем короли, дамы и т. д. Элементы (карты) мысленно делятся на уже «готовую последовательность» и неправильно расположенную последовательность. Теперь на каждом шаге, начиная с i = 2, из неправильно расположенной последовательности извлекается очередной элемент и перекладывается в готовую последовательность на нужное место.

 Скачать реферат