Алгоритмы на Python

Разбивайте текст на последовательности токенов из словаря и исследуйте неоднозначность токенизации.

Различайте задачу и её экземпляр; находите решения экземпляров задачи токенизации.

Спроектируйте алгоритм двусоставной токенизации: фиксируйте число токенов, перебирайте разрезы, обрабатывайте крайние случаи.

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

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

Сформулируйте предусловия и постусловия для алгоритма токенизации.

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

Используйте инварианты цикла, чтобы доказать корректность алгоритма.

Найдите один экземпляр входных данных, доказывающий, что алгоритм не корректен.

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

Исследуйте, как время выполнения алгоритма меняется при росте размера входа: линейный рост, постоянное время и квадратичный рост.

Научитесь оценивать временную сложность алгоритмов с помощью O-нотации: $O(1)$, $O(n)$, $O(n^2)$.

Оцените время выполнения циклов, перемножая число итераций на стоимость одной итерации.

Узнайте, почему срезы строк в Python имеют скрытую стоимость $O(n)$ и превращают линейный цикл в квадратичный алгоритм.

Оцените скрытую издержку оператора in для списка и выведите итоговую временную сложность алгоритма-токенизатора.

Замените список на множество, чтобы ускорить поиск элемента и снизить временную сложность с $O(n^2 + nk)$ до $O(n^2)$.