4.Типы рекурсий.

• Рекурсия, при которой рекурсивные вызовы на любом рекурсивном срезе,

инициируют не более одного последующего рекурсивного вызова,

называется линейной. Это наиболее простой и часто встречающийся тип

рекурсии.

♣Частный случай линейной рекурсии с отсутствующими

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

♣Этот тип рекурсии определяется как дополнительный к линейному. Иными словами, рекурсию называют каскадной, если она не является линейной. Пример функции: вычисление чисел Фибоначчи.

♣Циклическая последовательность вызовов нескольких функций F1, F2, …, Fk (процедур,

алгоритмов) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1),

называют косвенной или взаимной рекурсией.

• Рекурсия называется удаленной, если в теле функции при рекурсивных вызовах, в

выражениях, являющихся фактическими параметрами, снова встречаются

рекурсивные вызовы этой функции. Пример: функция Аккермана.

5.Основные понятия и определения алгоритмов сортировок. Алгоритм сортировки — это алгоритм упорядочения элементов. Из элементов состоят следующие типы и

структуры данных: массивы, строки, списки, файлы. Время — основной параметр,

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

временное хранение данных. Время выполнения: Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A.

Если на вход алгоритму подаётся множество A, состоящее из n элементов, то обозначим n=|A| . Для типичного алгоритма :

хорошее (среднее) поведение — O( n*Log(n) )

плохое поведение — O(n2)

идеальное поведение — O(n).

Требуемая память: Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют памяти

O(log(n)). При оценке не учитывается место, которое занимает исходный массив.

Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

6.Классификации алгоритмов сортировки.

По расположению элементов. •Устойчивость — устойчивая сортировка не меняет взаимного расположения равных элементов.

• Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.

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

По расположению множества элементов.

Внутренняя сортировка оперирует с массивами, целиком помещающимися в

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

обычно упорядочиваются на том же месте, без дополнительных затрат.

– Доступ к элементу произвольный.

– Объём данных позволяет им разместиться в ОЗУ.

Внешняя сортировка оперирует с запоминающими устройствами большого

объёма, но с доступом не произвольным, а последовательным (упорядочение

файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на

перемотку по сравнению с памятью неоправданно велики. Это накладывает

некоторые дополнительные ограничения на алгоритм и приводит к

специальным методам упорядочения, обычно использующим

дополнительное дисковое пространство. Кроме того, доступ к данным на

носителе производится намного медленнее, чем операции с оперативной

памятью.

– Доступ к носителю осуществляется последовательным образом: в каждый момент

времени можно считать или записать только элемент, следующий за текущим.

– Объём данных не позволяет им разместиться в ОЗУ.