Возведение в целую степень

1. В начале результат равен \(x\).
2. Записать \(n\) в двоичной системе счисления
3. Заменить в этой записи каждую из \(1\) парой букв КХ, а каждый \(0\) – буквой К
4. Вычеркнуть крайнюю левую пару КХ
5. Читая полученную строку слева направо, встречая букву К возвести результат в квадрат, а встречая букву X – умножить результат на \(x\).

• число операций умножения равно количеству цифр в двоичном представлении \(n\) в лучшем случае, и \(2(n-1)\) в худшем случае
• Временная сложность \(T(n) = O(\log n)\).
• Дополнительной памяти практически не требуется (если вместо записи \(KX\) сразу применять операции), и она не зависит от входных данных
• Пространственная сложность \(S(n) = O(1)\).
• “Наивная” реализация – \(O(n)\)

Умножение целых

• Первый множитель последовательно умножается на два
• второй – делится нацело на 2
• Результаты записываются в два столбика, пока во втором не получится 1.
• Результат умножения – сумма чисел первого столбика, напротив которых стоят нечётные числа во втором столбике.

• \(2 \log_2 n\) операций сдвига, где \(n\) – меньшее из двух чисел
• В худшем случае \(\log_2 n - 1\) операций сложения
• В любом случае, временная сложность \(T(n) = O(\log n)\).
• Для эффективной реализации алгоритма (если сразу суммировать числа), дополнительной памяти практически не требуется, и она не зависит от входных данных, поэтому \(S(n) = O(1)\)

Пример

• Результат \(43+86+172+688 = 989\)
• 10 операций сдвига и 4 операции сложения. \(\log_2(23) \approx 4.52\).

Линейный поиск

• сложность \(O(n)\) операций сравнения.

Поиск минимального элемента

• Сложность алгоритма \(O(n)\)

Бинарный поиск в упорядоченном массиве

Постановка

Имеется упорядоченный по возрастанию массив \(a\) размера \(n\) (индексация с 1), найти индекс элемента равного \(P\)

Простые сортировки

Сортировка “пузырьком”

Идея:

for m from n-1 to 1
  for j from 1 to m
    if a[j] > a[j+1]
      swap(a[j], a[j+1])
    end if
  end for j
end for m

Сортировка выбором

for i from 1 to n - 1
  min := i

  for j from i + 1 to n
     if a[j] < a[min]
        min := j
     end if
  end for j

  if indexMin ≠ i
     swap(a[min], a[i])
  end if
end for i

Сложность: \(n(n-1)/2 = O(n^2)\) операций сравнения. Не более \(n-1 = O(n)\) обменов.

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

for i from 2 to n
    x := a[i]
    j := i
    while (j > 1 and a[j-1] > x)
        a[j] := a[j-1]
        j := j - 1
    end while
    a[j] := x
end for i

• сложность по сравнениям \(1+2+\ldots+n-1\) \(=n(n-1)/2\) \(= O(n^2)\)
• сложность по присваиваниям \(O(n^2)\).

• сложность по присваиваниям можно улучшить до \(O(n)\)
• сложность по сравнениям можно улучшить до \(O(n\log n)\)
• скомбинировать – нельзя, худшая сложность всегда \(O(n^2)\)

Сортировка слиянием

algorithm merge_sort(a[n])
  if n ≤ 1
    return a

  mid := n/2

  left := merge_sort(a[1..mid])
  right := merge_sort(a[mid+1..n])

  return merge(left, right)
end algorithm merge_sort

algorithm merge(a[n], b[m])
  result := new array[n+m]
  i := 1
  j := 1
  k := 1
  while (i ≤ n and j ≤ m)
    if a[i] < b[j]
      result[k] := a[i]
      i := i+1
    else
      result[k] := b[j]
      j := j+1
    end if
    k := k+1
  end while
  while (i ≤ n)
    result[k] := a[i]
    k := k+1
    i := i+1
  end while
  while (j ≤ m)
    result[k] := b[j]
    k := k+1
    j := j+1
  end while
  return result
end algorithm merge

• \(t(n) = 2t(n/2)+c\cdot n\)
• \(t(1) = O(1) = c\)

• Можно показать, что сортировка, основанная на бинарном сравнении, не может иметь сложность ниже \(O(n\log n).\)

Сортировка подсчётом

• Возможно ли производить сортировку быстрее, чем за \(\mathcal O(n\log n)\)?
• За шаг алгоритма нужно получать больше информации, чем даёт сравнение.
• Простейший вариант – сортировка подсчётом.

• Рассмотрим \(\brace{x_i},\) \(N=|\brace{x_i}|\)
• \(0 \le x_i < \overline x\)
• \(x_i \in \mathbb Z\)
• Построим \(\brace{c_j},\)
• \(c_j = \underset{\brace{x_i}}{\mathrm{count}}(j)\)
• Сложность построения \(\brace{c_j}\) – \(\mathcal O(N).\)
• Из \(\brace{c_j}\) построим отсортированный массив \(\brace{x_k}\)
• Сложность построения \(\brace{x_k}\) – \(\mathcal O(\overline x).\)

• Сложность алгоритма – \(\mathcal O(N+\overline x),\)
• \(\mathcal O(N)\) если \(\overline x\) – константа.
• Осмысленно только если \(\overline x \ll N\)
• пространственная сложность \(\mathcal O(\overline x),\)
• при \(\overline x = 2^{64},\) – по меньшей мере 18 эксабайт (18·10¹⁸ байт, 18 млн терабайт)

Поразрядная сортировка (radix sort)

• основана на сортировке подсчётом
• для сортировки чисел в \(P\)-ичной системе счисления, достаточно поразрядной сортировки
• сортировку подсчётом применяется к каждому разряду последовательно
• сложность примерно \(\mathcal O(N\log_P \overline x)=\mathcal O(N).\)

algorithm radix_sort(a[N])
  for r from 1 to K
    for j from 1 to P-1
      c[j] := 0
    end for i
    for i from 1 to N
      x := r-тый разряд a[i]
      c[x] := c[x] + 1
    end for i

    for j from 1 to P-1
      c[j] := c[j-1] + c[j]
    end for i
    for i from N to 1
      x := r-тый разряд a[i]
      c[x] := c[x] - 1
      b[c[x]] := a[i]
    end for i
    a := b
  end for r
end algorithm radix_sort

• Сложность \(\mathcal O(K\cdot(P+N)) = \mathcal O((P+N)\ceil{\log_P \overline x}).\)
• Если \(\overline x\) и \(P\) константы, сложность \(\mathcal O(N)\)
• осмысленно если \(N\gg P\) и \(\overline x \ll N\)
• пространственная сложность \(\mathcal O(N+P)\)