Конспект установочных лекций по комплексному курсу Информатика, Теория информации

       

Heapsort через деревья выбора


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

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

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

Методы сортировки insertsort и  selectsort имеют среднюю временную сложность O(n2). При этом требуется n шагов вставки и выбора, а на i-м шаге затраты на вставку равны i, а на выбор n-i. В обоих случаях получается следующая формула для затрат:

n        n-1

å i=å(n-1)=n*(n-1)/2=O(n2).

i=1        i=0

Если последовательность в процессе сортировки хранится целиком в оперативной памяти, то говорят о внутренней сортировке. Если же последовательность хранится во внешней памяти, например, организована в файлы, то говорят о внешней сортировке.

Как правило быстрая сортировка (quicksort) наиболее удобна для внутренней сортировки больших последовательностей со случайным упорядочением элементов. Для внешней сортировки предпочтительнее метод слияния.

Пути в графах

Многие практические задачи информатики могут быть отображены на отношения и графы. При этом типичны проблемы, связанные с существованием путей в графах. Простейшей постановкой задачи, например, является достижимость (существование пути) в графе, которая родственна образованию транзитивного замыкания для отношения. Другие часто используемые алгоритмы решают вопрос о равенстве структур графов, например, установление изоморфности графов, или другие вопросы эквивалентности.



Содержание раздела