Неделя 3

Семинар. Квадратичные и линейные сортировки

скачать .ipynb lab03_tests.py lsd-example.tex

Семинар 3. Квадратичные и линейные сортировки

На этой паре вы напишете проверку упорядоченности и несколько сортировок, снимете время и увидите, когда линейный метод обгоняет sorted. Лекция дала инварианты и картинки, а не готовые циклы: циклы собираете вы.

Часть работы — упражнения в ячейках: график, замер, all/any, NaN, Fool, пузырёк, вставки, выбор, LSD. Их тестер не проверяет — смотрите на вывод сами. Четыре задачи с input/print — основа сдачи; пятая — запас, если закрыли первые четыре; шестая со звёздочкой — в самом конце, на паре её не разбираем.

Сдаёте этот файл семинаристу. ДЗ к лекции 3 — отдельная страница (LaTeX, монетка выбирает вставки или выбор): https://learn.ai.msu.ru/algo/1/03/hw-lecture/ — сдаёте лектору, не семинаристу; код туда не писать.

На больших тестах квадрат не успеет: тестер даёт TLE (лимит 2 секунды на тест), а не только «не тот ответ».

Можно спрашивать соседа и семинариста. Готовое решение копировать не стоит: тесты это не заменят, а на зачёте рядом никого не будет.

Как устроен ноутбук

Как на семинарах 1–2: ячейки Markdown и Code; командный режим — Esc, правка — Enter; Shift+Enter выполняет ячейку.

Скачайте с сайта курса этот файл .ipynb и файл lab03_tests.py в одну папку. Без файла тестов проверка не запустится. Откройте ноутбук из этой папки.

Ввод, вывод и тесты

Решение — функция без аргументов: внутри input и print, как в контесте. Тест подставляет входы сам. Не заполняйте поле ввода Jupyter.

В каждой задаче стоит заглушка: она что-то читает и печатает неверный ответ. Сначала запустите ячейку: увидите «не OK» или TLE, вход, «ожидалось» и «получено». Потом замените тело функции.

Импорт тестов стоит в каждой ячейке с решением. Если перезапустите ядро, достаточно снова выполнить эту ячейку — отдельно «подключать библиотеку в начале» не обязательно, хотя общая ячейка ниже тоже есть.

In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]

from lab03_tests import (
    test_task1,
    test_task2,
    test_task3,
    test_task4,
    test_task5,
    test_task6,
)

print('Тесты подключены')

Порядок работы

  1. Замеры и графики: %timeit, time.perf_counter, Matplotlib.
  2. all/any, проверка неубывания — задача 1.
  3. Функции как объекты, sort(key=…), устойчивость.
  4. NaN и сломанное сравнение.
  5. Квадратичные сортировки: Fool, пузырёк, вставки, выбор — задача 2, задача 3.
  6. Линейные: подсчёт — задача 4, LSD — задача 5 (запас).
  7. Сравнение с sorted и задача 6*.

Ячейки с комментарием «Ваш эксперимент» тестер не проверяет: это место, чтобы потрогать руками и посмотреть на вывод.

Среда: график и замер

При работе с алгоритмами полезно видеть, как время растёт с $n$, а не только верить формуле. Библиотека Matplotlib рисует графики; документация — на matplotlib.org.

Подключаем так:

import matplotlib.pyplot as plt

Если множество точек $(x, y)$ изображает зависимость $y$ от $x$, точки соединяют линией: plt.plot(x, y). Чтобы Jupyter не печатал служебный объект, в конце вызывают plt.show(). Оформление статьи не нужно: нарисовали и пошли.

In [ ]:
import matplotlib.pyplot as plt

x = [1, 2, 3, 4, 5]
y = [1, 4, 9, 16, 25]
plt.plot(x, y)
plt.show()

Один замер — это ещё не $\Theta$. Магия Jupyter %timeit много раз запускает маленькую функцию и сообщает типичное время. Для набора точек «время от $n$» удобнее time.perf_counter: засекли до и после, записали разность, повторили для нескольких $n$, нарисовали.

In [ ]:
def square_pass(n):
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1
    return s


%timeit square_pass(200)
In [ ]:
import time
import matplotlib.pyplot as plt


def square_pass(n):
    s = 0
    for i in range(n):
        for j in range(n):
            s += 1
    return s


ns = [50, 100, 150, 200, 250, 300]
times = []
for n in ns:
    t0 = time.perf_counter()
    square_pass(n)
    times.append(time.perf_counter() - t0)

plt.plot(ns, times)
plt.show()

Точки ложатся на параболу: при удвоении $n$ время растёт примерно вчетверо. По одному замеру вывод не делают — нужна серия точек. Смотрите на отношение времён, а не на «0.01 с — это быстро»: слишком маленькое $n$ тонет в шуме, печать и ввод в замер лучше не включать.

In [ ]:
# Ваш эксперимент: линейная функция и её график рядом с square_pass.
# Сравните время при n = 300 и n = 600 — во сколько раз выросло?

all, any и итерируемые объекты

all — это «логическое и по всей последовательности»: истинно, только если истинны все элементы. any — «логическое или»: достаточно одного истинного.

Пустой вход у all принято считать истинным (ложных элементов нет), у any — ложным.

Напишите одну редукцию своими руками — my_all. Вторую (any) возьмите стандартную.

In [ ]:
def my_all(iterable):
    """Верните True, если все элементы истинны. Пустой вход — True."""
    ...


print(my_all([True, True, True]))
print(my_all([True, False, True]))
print(my_all([]))
print(my_all(x % 2 == 0 for x in [2, 4, 8]))
print(my_all(x % 2 == 0 for x in [2, 3, 8]))

В Python довольно много объектов, по которым можно пройтись циклом for. Строка перебирается по символам — «как монах перебирает чётки». Список — по элементам, range — по числам. Такие объекты называются итерируемыми.

Генератор x % 2 == 0 for x in a тоже итерируемый: значения появляются по одному, отдельный список из них собирать не обязательно. Стандартные all и any как раз принимают любой итерируемый объект.

In [ ]:
for char in "ABC":
    print(char)

print(any(x < 0 for x in [1, 2, 3]))
print(any(x < 0 for x in [1, -2, 3]))
print(any([]))
print(all([]))

Проверку «массив не убывает» удобно записать редукцией по соседним парам:

all(a[i] <= a[i + 1] for i in range(len(a) - 1))

Пустой массив и массив из одного элемента соседних пар не дают — генератор пуст, all возвращает True. Не путайте «не убывает» ($a_i \le a_{i+1}$) со «строго возрастает» ($a_i < a_{i+1}$): знаки > и >= отвечают на разные вопросы.

In [ ]:
def is_nondecreasing(a):
    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))


print(is_nondecreasing([]))
print(is_nondecreasing([7]))
print(is_nondecreasing([1, 2, 2, 4]))
print(is_nondecreasing([1, 3, 2]))
print(is_nondecreasing([-5, -1, -1, 3]))
In [ ]:
# Ваш эксперимент: какой знак отвечает на вопрос «не убывает»?
# Проверьте [1, 2, 2], [], [7] для <= , < , > , >= и выберите верный.

Задача 1. Проверка неубывания

Дан массив целых чисел. Выведите YES, если массив упорядочен по неубыванию, то есть $a_1 \le a_2 \le \ldots \le a_n$, и NO иначе.

Вход. Первая строка: целое $n$ ($1 \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 10^9$).

Выход. Одно слово: YES или NO.

-> 5
-> 1 2 2 4 9
--
<- YES

-> 4
-> 1 3 2 4
--
<- NO

-> 3
-> 7 7 7
--
<- YES

-> 1
-> 0
--
<- YES

-> 4
-> -5 -1 -1 3
--
<- YES

-> 3
-> -1 -3 0
--
<- NO
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task1


def task1():
    n = int(input())
    a = list(map(int, input().split()))
    print("NO")


test_task1(task1)

Функция как объект и ключ сортировки

В Python функции — объекты первого класса. Наравне с числами и строками их можно:

  1. присваивать переменным,
  2. класть в списки,
  3. передавать в другую функцию как параметр,
  4. возвращать из функции как значение.

Имя функции связывается с объектом функции так же, как имя переменной — с её значением.

In [ ]:
def foo(x):
    return 10 * x


bar = foo
print(bar(5))


def apply_twice(function, x):
    return function(function(x))


print(apply_twice(foo, 3))

Часто имя не нужно: нужен временный объект функции «здесь и сейчас». Тогда пишут lambda:

lambda список_переменных: выражение

И у метода list.sort, и у функции sorted есть параметр key. Это функция, которую вызывают для каждого элемента перед сравнением. Сортируются сами элементы, а порядок задают ключевые значения.

На одинаковых ключах стандартная сортировка CPython устойчива: относительный порядок таких элементов не меняется. Это видно на словах одинаковой длины.

In [ ]:
s = "Клара у Карла украла кораллы, Карл у Клары украл кларнет."
words = s.replace(",", "").replace(".", "").split()
print(words)
words.sort(key=len)
print(words)

Если сортировать пары (ключ, нагрузка) как есть, Python сравнивает оба поля: при равном ключе решит нагрузка. Нагрузка сама по себе ключом не является. Чтобы сравнивать только ключ, в key должна попасть функция, которая из пары достаёт ключ.

Безымянная lambda как раз удобна как такое «достать поле». Посмотрите, чем отличается сортировка пар целиком от сортировки по одному полю.

In [ ]:
pairs = [(1, 9), (2, 0), (1, 3), (2, 1)]
print(sorted(pairs))            # сравниваются оба поля
print(sorted(pairs, key=len))   # у всех пар длина 2 — порядок не задан ключом
In [ ]:
# Ваш эксперимент: упорядочите пары только по первому полю.
pairs = [(1, 9), (2, 0), (1, 3), (2, 1)]
# Допишите вызов sorted(pairs, key=...) и сравните с sorted(pairs).

NaN и сломанное сравнение

float('nan') — нечисло IEEE, не «очень большое» и не «очень маленькое». Любое сравнение с ним ложно: и nan < x, и x < nan, и nan < nan. Это не про камень-ножницы-бумагу с лекции: там цикл в правилах игры, здесь сломанное отношение на float.

list.sort опирается на сравнения. Если в массиве есть nan, «порядок» после a.sort() смотрите глазами: он не обязан совпасть с тем, что вы ждёте от чисел. Запомните картинку — в конце ноутбука есть задача со звёздочкой, где это всплывёт.

In [ ]:
nan = float("nan")
print(nan < 1, 1 < nan, nan < nan, nan == nan)

a = [3.0, nan, 1.0, 2.0]
print(a)
a.sort()
print(a)
print(all(a[i] <= a[i + 1] for i in range(len(a) - 1)))
In [ ]:
# Ваш эксперимент: поставьте nan в начало, в середину и в конец.
# Что делает sorted(a) в каждом случае? Похож ли результат на «числа по порядку»?

Квадратичные сортировки

На лекции был Fool: повторять прогон соседних обменов, пока проверка не скажет «готово». Вложенного for может не быть — время в худшем случае всё равно квадрат: отсутствие вложенных циклов не гарантия линейности.

Напишите Fool сами. Затем замерьте его на случайном массиве: график должен напоминать параболу, как у square_pass.

In [ ]:
import time
import random
import matplotlib.pyplot as plt


def is_nondecreasing(a):
    return all(a[i] <= a[i + 1] for i in range(len(a) - 1))


def fool_sort(a):
    # Повторяйте прогон / обмен соседей, пока проверка не скажет «готово».
    ...
    return a


print(fool_sort([2, 3, 1]))  # ожидается [1, 2, 3]

random.seed(1)
ns = [50, 80, 110, 140]
times = []
for n in ns:
    a = [random.randrange(n) for _ in range(n)]
    t0 = time.perf_counter()
    fool_sort(a)
    times.append(time.perf_counter() - t0)

plt.plot(ns, times)
plt.show()

Если график похож на параболу, при удвоении $n$ время растёт примерно вчетверо. Кода без вложенного for достаточно, чтобы вести себя как квадратичный: прогонов тоже порядка $n$.

In [ ]:
# Ваш эксперимент: замерьте Fool на обратно упорядоченном массиве
# (list(range(n, 0, -1))) и на «почти порядке». Где быстрее и почему?

Пузырёк — тот же прогон, но заранее известно, сколько раз и какую длину ещё смотреть: после $k$ проходов $k$ наибольших уже на своих местах справа (держите один вариант, как на лекции).

На почти упорядоченном входе помогает ранний выход: проход без обменов значит «готово». Замерьте случайный массив и массив «почти порядок, одна инверсия»: у пузырька с ранним выходом второе должно быть заметно быстрее.

In [ ]:
import time
import random


def bubble_sort(a):
    # Прогоны соседних обменов; можно выйти раньше, если проход ничего не менял.
    ...
    return a


print(bubble_sort([4, 3, 2, 1]))  # ожидается [1, 2, 3, 4]

n = 400
random_a = [random.randrange(n) for _ in range(n)]
almost = list(range(n))
almost[0], almost[1] = almost[1], almost[0]

t0 = time.perf_counter()
bubble_sort(random_a)
print("случайный:", time.perf_counter() - t0)

t0 = time.perf_counter()
bubble_sort(almost)
print("почти порядок:", time.perf_counter() - t0)

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

Выбор и вставки — по картинкам лекции, не по готовому коду.

  • Выбор: префикс длины $k$ — $k$ наименьших; каждый шаг минимум хвоста меняется с границей префикса.
  • Вставки: префикс длины $k$ уже упорядочен; новый элемент въезжает на своё место сдвигами.

Оба в худшем случае $\Theta(n^2)$ сравнений. Вставки обычно дешевле на почти упорядоченном входе. Выбор адаптивным не бывает: он всегда просматривает весь хвост. Доказывать инвариант на паре не нужно: это текст ДЗ к лекции (монетка, LaTeX), сдаёте лектору.

Напишите оба и замерьте случайный и почти упорядоченный входы.

In [ ]:
import time
import random


def selection_sort(a):
    ...
    return a


def insertion_sort(a):
    ...
    return a


print(selection_sort([3, 1, 2, 3, 0]))  # ожидается [0, 1, 2, 3, 3]
print(insertion_sort([3, 1, 2, 3, 0]))  # ожидается [0, 1, 2, 3, 3]

n = 400
random_a = [random.randrange(n) for _ in range(n)]
almost = list(range(n))
almost[-1], almost[-2] = almost[-2], almost[-1]

for name, fn in [("выбор", selection_sort), ("вставки", insertion_sort)]:
    t0 = time.perf_counter()
    fn(random_a[:])
    t_rand = time.perf_counter() - t0
    t0 = time.perf_counter()
    fn(almost[:])
    t_almost = time.perf_counter() - t0
    print(name, "случайный:", t_rand, "почти порядок:", t_almost)

На случайном входе выбор и вставки одного порядка; на почти упорядоченном вставки обычно резко ускоряются, а выбор — нет.

In [ ]:
# Ваш эксперимент: устойчивы ли ваши вставки и выбор?
# Возьмите пары [(2, 9), (1, 5), (2, 3), (1, 7)] и упорядочьте их по первому
# полю своей функцией. Сохранился ли порядок нагрузок при равных ключах?

Свой цикл на маленьком $n$ успеет. Стандартный sorted тесты тоже примут: цель ячейки — потренировать ввод-вывод и один из алгоритмов пары, а не античит.

Задача 2. Сортировка массива

Дан массив целых чисел. Выведите его элементы в порядке неубывания.

Вход. Первая строка: целое $n$ ($1 \le n \le 3\cdot 10^3$). Вторая строка: $n$ целых чисел $a_i$ ($|a_i| \le 10^9$).

Выход. Одна строка из $n$ чисел через пробел.

-> 5
-> 3 1 2 3 0
--
<- 0 1 2 3 3

-> 1
-> -10
--
<- -10

-> 4
-> 4 3 2 1
--
<- 1 2 3 4
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task2


def task2():
    n = int(input())
    a = list(map(int, input().split()))
    print(*a)


test_task2(task2)

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

Задача 3. Устойчивая сортировка пар

Даны $n$ пар целых чисел $(k_i, p_i)$. Упорядочьте пары по неубыванию только ключа $k$. Поле $p$ — полезная нагрузка: само по себе оно ключом не является.

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

Вход. Первая строка: целое $n$ ($1 \le n \le 10^5$). Далее $n$ строк: по два целых $k$ и $p$ ($|k|, |p| \le 10^9$).

Выход. $n$ строк k p в требуемом порядке.

-> 4
-> 3 10
-> 1 20
-> 2 30
-> 4 40
--
<- 1 20
<- 2 30
<- 3 10
<- 4 40

-> 4
-> 1 5
-> 2 8
-> 1 3
-> 2 1
--
<- 1 5
<- 1 3
<- 2 8
<- 2 1

-> 3
-> 1 9
-> 1 8
-> 1 7
--
<- 1 9
<- 1 8
<- 1 7

-> 3
-> 5 1
-> 4 2
-> 3 3
--
<- 3 3
<- 4 2
<- 5 1
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task3


def task3():
    n = int(input())
    for _ in range(n):
        k, p = map(int, input().split())
        print(k, p)


test_task3(task3)

Линейные сортировки

Если диапазон ключей мал и известен, индекс массива снова может значить значение, как частоты на семинаре 2. Сводка «сколько раз встретился ключ $v$» плюс выписывание ключей по возрастанию даёт время $\Theta(n + U)$, где $U$ — размер диапазона, а не $n^2$.

Не путайте $n$ (длина входа) и $U$ (сколько разных ключей возможно). Квадрат по $n$ на задаче 4 получит TLE. Вызывать sorted условие не запрещает: на таком $n$ в Python он, скорее всего, тоже успеет.

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

Дан массив целых чисел из диапазона от $0$ до $1000$ включительно. Выведите массив в порядке неубывания.

Вход. Первая строка: целое $n$ ($1 \le n \le 2\cdot 10^5$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i \le 1000$).

Выход. Одна строка из $n$ чисел через пробел.

-> 6
-> 3 1 3 2 1 3
--
<- 1 1 2 3 3 3

-> 5
-> 7 7 7 7 7
--
<- 7 7 7 7 7

-> 4
-> 1000 0 1000 0
--
<- 0 0 1000 1000
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task4


def task4():
    n = int(input())
    a = list(map(int, input().split()))
    print(*a)


test_task4(task4)

LSD. Если числа одной разрядности, их можно сортировать устойчивыми проходами с младшего разряда: каждый проход — устойчивый подсчёт по одной цифре. После $k$ проходов порядок правильный по $k$ младшим разрядам.

Готовый цикл с лекции (карточки и палочка) сюда не копируйте: напишите короткий проход сами. Двоичный пример на три-четыре бита или десятичные цифры — как удобнее. Если времени мало, оставьте упражнение и не открывайте задачу 5.

In [ ]:
def digit(x, power10):
    """Цифра числа x на разряде 10 ** power10 (0 — единицы)."""
    return (x // (10 ** power10)) % 10


def lsd_sort(a, d):
    # d устойчивых проходов, начиная с младшего разряда.
    ...
    return a


print(lsd_sort([15, 7, 100, 3], 3))     # ожидается [3, 7, 15, 100]
print(lsd_sort([10, 10, 1, 0, 99], 2))  # ожидается [0, 1, 10, 10, 99]

Если осталось время

Задача 5 не обязательна. Если 1–4 уже зелёные — можно закрыть и её. Квадрат по $n$ на больших тестах не успеет.

Задача 5. Сортировка чисел фиксированной разрядности

Даны $n$ неотрицательных целых чисел. Каждое из них меньше $10^d$, то есть записывается не более чем $d$ десятичными цифрами (ведущие нули не печатать). Выведите числа в порядке неубывания.

Вход. Первая строка: $n$ и $d$ ($1 \le n \le 10^5$, $1 \le d \le 6$). Вторая строка: $n$ целых чисел $a_i$ ($0 \le a_i < 10^d$).

Выход. Одна строка из $n$ чисел через пробел.

-> 4 3
-> 15 7 100 3
--
<- 3 7 15 100

-> 3 1
-> 9 0 5
--
<- 0 5 9

-> 5 2
-> 10 10 1 0 99
--
<- 0 1 10 10 99
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task5


def task5():
    n, d = map(int, input().split())
    a = list(map(int, input().split()))
    print(*a)


test_task5(task5)

Когда выигрывает подсчёт

sort / sorted в CPython — Timsort, примерно $n\log n$ сравнений и очень хорошо написан. Подсчёт выигрывает, когда диапазон $U$ мал, а $n$ велико: нет сравнений ключей, только проходы по входу и по $U$. Плата — дополнительная память $\Theta(U)$ под массив частот.

Если $U$ огромный (ключи до $10^9$), массив частот не построите. Если $n$ маленькое, разница часто не видна за шумом замера. Снимите sorted и свой подсчёт на одном и том же большом массиве из диапазона $0..1000$.

In [ ]:
import time
import random


def counting_sort(a, u=1000):
    ...
    return a


n = 20000
a = [random.randrange(1001) for _ in range(n)]

t0 = time.perf_counter()
sorted(a)
print("sorted:", time.perf_counter() - t0)

t0 = time.perf_counter()
counting_sort(a[:])
print("подсчёт:", time.perf_counter() - t0)
In [ ]:
# Ваш эксперимент: прикиньте число операций для n = 200000, U = 1000
# и для того же n, но с ключами до 10**9 (массив частот такого размера
# не построить). Что выгоднее в каждом случае?

* Задача 6. Гномья сортировка

Не требуется для зачёта пары. На паре эталон не разбираем. Кто закрыл 1–4 и хочет звёздочку — в конце ноутбука.

Рассмотрим такой процесс над массивом. Стоим в начале (индекс $0$). Пока индекс меньше длины массива:

  • если индекс равен $0$ или текущий элемент не строго меньше предыдущего — шаг вперёд;
  • иначе меняем текущий элемент с предыдущим местами и делаем шаг назад.

Примените этот процесс к данному массиву и выведите массив после него.

Во входе могут встречаться значения nan (нечисло IEEE). Проверяется точная последовательность токенов, а не «любой разумный порядок».

Обычные sorted и list.sort, скорее всего, не совпадут с эталоном на тестах с nan. Можно попробовать обхитрить тест: вызвать стандартную сортировку и расставить nan так, чтобы ответ совпал с описанным процессом.

Вход. Первая строка: целое $n$ ($1 \le n \le 3\cdot 10^3$). Вторая строка: $n$ токенов — целые числа или слово nan (в нижнем регистре). Модуль каждого конечного числа не превосходит $10^9$.

Выход. Одна строка из $n$ токенов через пробел: те же целые и nan.

-> 5
-> 3 1 2 3 0
--
<- 0 1 2 3 3

-> 4
-> 2 0 nan 1
--
<- 0 2 nan 1

-> 3
-> 7 7 7
--
<- 7 7 7

-> 1
-> nan
--
<- nan
In [ ]:
import sys
from pathlib import Path

sys.path[:0] = [str(Path.cwd())]
from lab03_tests import test_task6


def task6():
    n = int(input())
    a = input().split()
    print(*a)


test_task6(task6)

Шпаргалка

  • Инвариант — утверждение, верное на границе итерации. Картинки — на лекции; доказательство вставок или выбора — в LaTeX-ДЗ лектору.
  • Устойчивость — при равных ключах относительный порядок входа сохраняется.
  • Ключ — то, по чему сравнивают; нагрузка в сравнение не входит.
  • Сложности в худшем случае: Fool, пузырёк, вставки, выбор — $\Theta(n^2)$; подсчёт — $\Theta(n + U)$; LSD — $\Theta(d(n + 10))$; sorted — примерно $n\log n$.
  • all([]) истинно, any([]) ложно.
  • nan ни с кем не меньше и не больше; проверка <= с ним ложна.
  • $n$ — длина входа, $U$ — размер диапазона ключей. Это разные величины.

Типичные сбои на паре: знак сравнения; nan в проверке порядка; квадрат там, где нужен линейный проход; пары сравнили целиком, и нагрузка вмешалась.

Сдача

Перед отправкой проверьте:

  • сохранили ноутбук: File → Save;
  • рядом с ноутбуком лежит lab03_tests.py;
  • в ячейке решения есть from lab03_tests import test_taskN (после перезапуска ядра выполните эту ячейку снова);
  • отправили этот файл .ipynb семинаристу в личные сообщения до дедлайна.

В LMS заданий семинара 3 ещё нет. ДЗ к лекции — https://learn.ai.msu.ru/algo/1/03/hw-lecture/ — сдаёте лектору, не семинаристу: .tex и PDF, не этот ноутбук.

Недорешенные задачи не мешают отправке: сдайте то, что успели. Красный тест у заглушки — нормально. TLE значит «слишком медленно», обычно квадрат там, где нужен линейный проход. Задача 5 не обязательна. Задача 6* для зачёта пары не нужна.