Оценка сложности: подсчет вместо поиска
- ?Сортировка подсчетом? (задача о сортировке большого количества двузначных чисел или других немногочисленных по типу объектов)
?Период псевдослучайной последовательности? (определить период последовательности вида ri=(aћri-1+b) mod m дял заданных a, b и m). (Codeforces): линейка из m возможных элементов, в которой отмечаются встреченные элементы (первый встреченный дважды элемент отмечает начало периода, первый встреченный трижды ? конец)
Более сложный случай: m настолько велико, что хранить m ячеек нельзя, зато i не превосходит разумного предела. Использование hash-таблицы (см. комментарий к решению первой задачи)
Домашнее задание
Прочитать про хеш-таблицы в Википедии Реализовать тип ?множество? для произвольно больших целых неотрицательных чисел. Программа должна уметь добавлять число в множество, удалять его оттуда и проверять, содержится ли число в множестве. В частности, должен быстро работать поиск по 106 элементам (например, 104 таких поисков
); пользоваться dict не разрешается 
. Решение: Придумаем функцию H(число), которая для любого числа дает результат в диапазоне, скажем, 0?105. Создадим список T пустых списков из 105 элементов. Тогда добавление числа будет происходит в список T[H(число)], равно как и удаление, и поиск. Тем самым поиск по большому списку сводится к индексированию и поиску по маленькому списку. H(x) ? это и есть хеш-функция, а T[] ? хеш-таблица
В качестве H(x) в случае случайных чисел можно взять просто x%10**5: longint_hash.py
Написать генератор тестовых данных (в частности, генератор длинных случайных чисел)" longint.py
Как будет выглядеть H(x), если x ? это строки маленьких латинских букв?
Определить, достаточно ли велик период последовательности вида ri=(aћri-1+b) mod m для заданных a, b и m при i < n << m. Решение: за хеш-функцию взять H(ri)=ri%10000. В таблице хранить не просто списки ri, для которых H(ri) одинаково, а пары вида (ri,количество_появлений) (то есть T[rk%10000]=[[ri, 0], [rj, 0], [rk, 0], ?]). Остальное см. выше.
![/!\](/moin_static197/modernized/img/alert.png "/!\")
MCCME Постройте все циклические перестановки строки, отсортируйте их и выпишите последний столбец. Вводится строка, состоящая из маленьких латинских букв, ее длина не превосходит 30000 символов.
Условные обозначения
? тема по Linux 
?? необязательная тема - ? теоретическое задание
? тема для самостоятельного изучения