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

• Поиск по неструктурированному множеству пар «ключ-объект»:
  • Чтение ключа: ~N операций
  • Сравнение ключей: ~N операций
• Поиск по упорядоченному множеству
  • Дополнительные условия: отношение порядка и прямой доступ к элементам
  • Алгоритм: половинное деление (бинарный поиск)
    • Чтение ключа: ~log₂N операций
    • Сравнение ключа: ~log₂N операций
• Сортировка
  • Операции чтения и записи объекта
• Сортировка выбором
  • Оценка сложности: (N-1)*(N-2)/2 ⇒ ~N²

  • Замечание: много паразитных сравнений

       1   for i in xrange(N-1):
       2       m = i
       3       for j in xrange(i+1,N):
       4           if A[m]>A[j]:
       5               m = j
       6       A[m], A[i] = A[i], A[m]
    

• Сортировка вставками: нужны «дешёвые» вставка и удаление (как в списке, а не как в массиве):
  • Идея: вставляем очередной элемент в упорядоченный список (N-1 шаг), при этом место вставки определяем бинарным поиском (log₂N сравнений)

       1   def binsert(el, seq, st, end):
       2     if end-st<2:
       3         seq.insert(st+(el>seq[st]),el)
       4     elif el<seq[(st+end)/2]:
       5         binsert(el, seq, st, (st+end)/2)
       6     else:
       7         binsert(el, seq, (st+end)/2, end)
       8 
       9   def insertsort(seq):
      10     for en in xrange(1,len(seq)):
      11         e = seq.pop(en)
      12         binsert(e, seq, 0, en)
    

  • ⇒ сложность ~N*log₂N

• Сортировка слиянием: нужна дополнительная память (возвращается новый список), зато достаточно последовательного доступа к элементам

     1 def joinsort(seq, st=0, en=None):
     2     if en-st<2: return seq[st:en]
     3     l = joinsort(seq, st, (st+en)/2)
     4     r = joinsort(seq, (st+en)/2, en)
     5     new = []
     6     while l and r:
     7         new.append((l if l[0]<r[0] else r).pop(0))
     8     new.extend(l)
     9     new.extend(r)
    10     return new
    11  
  

  • Половинное деление снова обеспечивает сложность ~N*log₂N

Домашнее задание

1. Первое

2. Определить функции Compare(), Read() и Write(), которые сравнивают два элемента последовательности, читают и пишут элемент соответственно, ведя при этом подсчёт совершённых операций. Запрограммировать алгоритмы сортировки так, чтобы использовались только эти функции. Сравнить количество сравнений, чтений и записей в разных алгоритмах.

Условные обозначения

• — тема по Linux

• ­— тема повышенной сложности

• — теоретическое задание

• — тема для самостоятельного изучения

CategoryClass CategoryVmsh