Анализ времени работы

 

Оценим время работы алгоритма сортировки подсчётом. Циклы в стро­ках 1-2 и 6-7 работают за время О(k), циклы в строках 3-4 и 10-11 – за время О(п), а весь алгоритм, стало быть, работает за время О(k + п). Если k =О(п), то время работы есть О(п).

Алгоритм сортировки подсчётом обладает важным свойством, называемым устойчивостью(is stable). Именно, если во входном массиве присутствует не­сколько равных чисел, то в выходном массиве они стоят в том же порядке, что и во входном. Это свойство имеет смысл, только если в массиве вместе с числами записаны дополнительные данные. К примеру, сортируются не просто числа, а пары , где t – число от 1 до k, а х – про­извольный объект, и требуется переставить их так, чтобы первые компоненты пар шли в неубывающем порядке. Описанный алгоритм позволяет это сделать, причём относительное расположение пар с равными первыми компонентами не меняется. Это свойство и называется устойчивостью.

 

 

3 Элементарные и нелинейные структуры данных

3.1 Элементарные структуры: список, стек, очередь, дек

 

Стеки и очереди – это динамические множества, в которых элемент, удаляе­мый из множества операцией Delete, не задаётся произвольно, а определяется структурой множества. Именно, из стека(stack) можно удалить только тот элемент, который был в него добавлен последним: стек работает по принципу «последним пришёл – первым ушёл» (last-in, first-out – сокращенно LIFO).Из очереди(queue), напротив, можно удалить только тот элемент, который на­ходился в очереди дольше всего: работает принцип «первым пришёл – первым ушёл» (first-in, first-out — сокращенно FIFO). Существует несколько способов эф­фективно реализовать стеки и очереди, причем в основе эффективных реализаций этих структур лежат списки, потому что это наиболее простой способ организовать структуру данных, состоящее из некоторого множества элементов.