Оценка сложности: подсчёт вместо поиска

• «Сортировка подсчётом» (задача о сортировке большого количества двузначных чисел или других немногочисленных по типу объектов)

• «Период псевдослучайной последовательности» (определить период последовательности вида r_i=(a·r_i-1+b) mod m дял заданных a, b и m). (Codeforces): линейка из m возможных элементов, в которой отмечаются встреченные элементы (первый встреченный дважды элемент отмечает начало периода, первый встреченный трижды — конец)

• Более сложный случай: m настолько велико, что хранить m ячеек нельзя, зато i не превосходит разумного предела. Использование hash-таблицы (см. комментарий к решению первой задачи)

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

1. Прочитать про хеш-таблицы в Википедии

2. Реализовать тип «множество» для произвольно больших целых неотрицательных чисел. Программа должна уметь добавлять число в множество, удалять его оттуда и проверять, содержится ли число в множестве. В частности, должен быстро работать поиск по 10⁶ элементам (например, 10⁴ таких поисков ); пользоваться dict не разрешается .

   • Решение: Придумаем функцию H(число), которая для любого числа даёт результат в диапазоне, скажем, 0…10⁵. Создадим список T пустых списков из 10⁵ элементов. Тогда добавление числа будет происходит в список T[H(число)], равно как и удаление, и поиск. Тем самым поиск по большому списку сводится к индексированию и поиску по маленькому списку. H(x) — это и есть хеш-функция, а T[] — хеш-таблица

   • В качестве H(x) в случае случайных чисел можно взять просто x%10**5: longint_hash.py

   • Написать генератор тестовых данных (в частности, генератор длинных случайных чисел)" longint.py

   • Как будет выглядеть H(x), если x — это строки маленьких латинских букв?

3. Определить, достаточно ли велик период последовательности вида r_i=(a·r_i-1+b) mod m для заданных a, b и m при i < n << m. Решение: за хеш-функцию взять H(r_i)=r_i%10000. В таблице хранить не просто списки r_i, для которых H(r_i) одинаково, а пары вида (r_i,количество_появлений) (то есть T[r_k%10000]=[[r_i, 0], [r_j, 0], [r_k, 0], …]). Остальное см. выше.

4. MCCME Постройте все циклические перестановки строки, отсортируйте их и выпишите последний столбец. Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.

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

• — тема по Linux

• ­— необязательная тема

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

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

CategoryClass CategoryVmsh