Предисловие

Здесь выкладываются некоторые материалы 10А класса 2020/2021 года обучения.

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

Асимптотическая сложность

Эта глава является вспомогательной для основной части. Здесь содержатся лишь некоторые моменты, облегчающие/углубляющие понимание материала, изложенного по вышеприведённой ссылке.

Свойства степеней

Договоримся, что, записывая \(a^b\), мы подразумеваем, что \(a>0\), а \(b\) — произвольное действительное число.

Полезно помнить следующие алгебраические свойства:

\(a^x \cdot b^x = (ab)^x\)
\(a^x \cdot a^y = a^{x+y}\)
\((a^x)^y = a^{xy} = (a^{y})^x\)

а также — следующие аналитические свойства:

если \(x>0\), то \(a>b\) равносильно \(a^x > b^x\)
если \(a>1\), то \(x>y\) равносильно \(a^x > a^y\)

Для равенства \(a=b^x\) используется равносильная запись \(\log_b a = x\). Также договоримся, что по умолчанию \(\log = \log_2\).

Если выписать для основания \(2\) релевантные свойства степеней из вышеприведённого списка, получится следующее:

\(2^x \cdot 2^y = 2^{x+y}\)
\((2^x)^y = 2^{xy} = (2^y)^x\)
\(x>y\) равносильно \(2^x > 2^y\)

Подставляя \(x=\log a\) и \(y=\log b\) в первое и третье свойства, получаем:

\(ab = 2^{\log a + \log b}\)
\(\log a > \log b\) равносильно \(a > b\)

Применяя к первому из получившихся свойств логарифм, получаем

\(\log (ab) = \log a + \log b\)

Наконец, подставляя \(y=\log a\) во второе из свойств степеней двойки, получим

\(a^x = 2^{x\log a}\)

из чего, применяя к обеим частям логарифм, получаем

\(\log (a^x) = x\log a\)

Итого свойства степеней в терминах логарифмов выглядят так:

\(\log (ab) = \log a + \log b\)
\(\log (a^x) = x\log a\)
\(a > b\) равносильно \(\log a > \log b\)

Немного неравенств

Начнём со вспомогательного неравенства

\[2^x > x\]

При \(x\lt 1\) оно очевидно, а при \(x\geqslant 1\) оно следует из неравенства Юнга

\( (1+1)^x \geqslant 1 + x\cdot 1 \)

Само неравенство Юнга для рациональных степеней является следствием неравенства Коши о средних, а для иррациональных следует из соображений монотонности.

Теперь сформулируем и докажем очень важное неравенство.

Асимптотическое неравенство между степенью и логарифмом

Для любого \(a > 0\) существует \(X\) такой, что при всех \(x > X\) выполнено

\[ x^{a} > \log x \]

Доказательство

Поскольку

\[ \log x = \log (x^a)^{1/a} = \frac{1}{a} \log (x^a) \]

то нам достаточно доказать, что есть такое \(Y\), что для всех \(y > Y\) выполнено

\[ y > \frac{1}{a} \log y \]

Но это неравенство эквивалентно

\[ 2^{ay} > y = \frac{ay}{a} \]

Поэтому нам достаточно доказать, что есть такое \(Z\), что для всех \(z > Z\) выполнено

\[ 2^z > \frac{z}{a} \]

Пусть \(z = \frac{2}{a} + h\). Тогда

\[ 2^z = 2^{2/a} \cdot 2^h > \frac{2}{a} \cdot h \]

Осталось обеспечить

\[ 2h > \frac{2}{a} + h \]

выбором

\[ Z = \frac{2}{a} + \frac{2}{a} = \frac{4}{a} \]

Вообще говоря, для разговора об асимптотической сложности достаточно доказать более слабое утверждение о том, что для любого \(a > 0\) существуют \(X\) и \(k>0)) такие, что при всех \(x > X\) выполнено

\[ x^{a} > k\log x \]

Для его доказательства достаточно выбрать \(k=a\) и перейти к эквивалентному (при замене \(y=x^a\)) неравенству

\[ y > \log y \]

которое следует из \(2^y > y\).

Классы асимптотической сложности

Пусть функция \(f\) является нижней асимптотической оценкой для \(g\): а именно, существуют такие \(X\) и \(k>0\), что для всех \(x>X\) выполнено

\[ k f(x) \lt g(x) \]

Заметим, что при этом \(g\) является верхней асимптотической оценкой для \(f\): для тех же \(x\) выполнено

\[ f(x) \lt \frac{1}{k} g(x) \]

Договоримся любую из этих ситуаций (а, следовательно, и обе) обозначать \(f\prec g\).

Для отношения \(\prec\) выполнены следующие свойства:

рефлексивность: \(f\prec g\)
транзитивность: из \(f\prec g\) и \(g\prec h\) следует \(f\prec h\)

Если \(f\prec g\) и \(g\prec f\), будем говорить, что \(f\) и \(g\) асимптотически эквивалентны и обозначать это \(f\equiv g\).

Поскольку отношение \(\equiv\) симметрично, то его можно рассматривать как рёбра графа, вершинами которого являются всевозможные функции (натурального аргумента). Компоненты связности этого графа мы будем называть классами сложности.

Очевидно, что если есть неравенство \(f\prec g\) между представителями классов сложности \(F\) и \(G\), то такое же неравенство есть между любой парой представителей этих классов. Поэтому, записывая, напимер, \(\log n\prec n\) мы будем этой записью подразумевать высказывание «любой представитель класса сложности логарифма является нижней асимптотической оценкой для любого представителя класса сложности линейной функции».

Нижеприведённые соотношения между классами (следующие из неравенства, доказанного в предыдущем разделе) полезно помнить: для всех \(a > 0\) и \(b > 0\)

\(1 \prec (\log n)^a\)
\((\log n)^a \prec n^b\)
\(n^a \prec 2^{n^b}\)

Все эти неравенства строгие: ни одна из указанных пар классов не совпадает.

Быстрые алгоритмы сортировки

Альтернативный вариант quicksort

В дополнение к достаточно сложному для понимания алгоритму разбиения из прошлогодних материалов мы приведём более простую альтернативу

def partition(a, left, right):
  pivot = a[left]  ## или любой другой элемент массива
  index = right-1  ## такой index работает только для a[left] 

  while left < right:
    if a[left] < pivot: left += 1
    else:
      right -= 1
      a[left], a[right] = a[right], a[left]

  a[left], a[index] = a[index], a[left]
  return left


def quicksort(array, left = 0, right = None):
  if right == None: right = len(array)

  if right - left <= 1: return

  pivot_index = partition(array, left, right)
  quicksort(array, left, pivot_index)
  quicksort(array, pivot_index+1, right)

Корректность разбиения partition здесь очевидна:

элементы с индексами, меньшими left, всегда меньше опорного
элементы с индексами, не меньшими right, всегда не меньше опорного
за каждую итерацию цикла разница между right и left уменьшается на 1, поэтому цикл завершается, а right не бывает меньше left
отсюда, в частности, следует, что right и left в момент обмена находятся в пределах массива

На практике вышеприведённый алгоритм работает примерно на 10% медленнее, чем тот, который приведён в прошлогодних материалах (впрочем, в реальности в чистом виде quicksort редко используется — есть существенно более сложные, но при этом и более эффективные схемы сортировки).

Связные списки

Автоматическая переассоциация бинарных операций

Каноническое слияние связных списков имеет вид

def concat(a, b):
  if is_empty(a): return b
  return join(head(a), concat(tail(a), b))

или же, в итеративном (левосвёрточном) варианте,

def concat(a, b):
  a = reverse(a)  ## предполагается, что reverse разворачивает список
  result = b

  while not is_empty(a):
    result = join(head(a), result)
    a = tail(a)

  return result

Вычислительная сложность такого алгоритма — длина первого входа. По этой причине выражение

concat(a1, concat(a2, concat(a3, ...)))

имеет линейную (по количеству входных списков) сложность, а выражение

concat(...concat(concat(a1, a2), a3) ... )

имеет квадратичную сложность.

В связи с этим очень актуальным является приём (по-видимому, впервые применённый в районе 1854 года математиком Артуром Кэли), позволяющий автоматически «прижимать» (или, по-научному, переассоциировать) все скобки в выражении, использующем некоторую бинарную операцию, вправо.

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

def wrap(x): return (lambda y: x-y)

Заметим, что функция wrap является обратимой: wrap(x)(0) == x. В связи с этим реализуем обращение

def unwrap(wrapped): return wrapped(0)

Каждое вычитание нужно заменить на

def sub(a, b): return (lambda x: a(b(x)))

После чего результат такой замены, произведённой над всей формулой, нужно обратить при помощи unwrap:

unwrap(sub(wrap(a), sub(wrap(b), wrap(c)))) ## (a-(b-c))
unwrap(sub(sub(wrap(a), wrap(b)), wrap(c))) ## тоже (a-(b-c))

В тех случаях (весьма редких на практике), когда wrap не является обратимым, приходится искусственно отделять самый правый лист формулы и применять к нему результат преобразования остальной части формулы.

Связь левой и правой свёрток

На настоящий момент является домашним заданием.

Lessons 10a21