Упражнения¶

1. Проведите эксперимент, подтверждающий, что оператор индекса для списков имеет \(O(1)\)
2. Проведите эксперимент, подтверждающий, что получение и запись элемента в словарь имеют \(O(1)\) for dictionaries.
3. Проведите эксперимент, сравнивающий производительность оператора del для словарей и списков
4. Для заданного списка чисел, расположенных в случайном порядке, напишите работающий за линейное время алгоритм поиска k-го наименьшего элемента. Объясните, почему ваш алгоритм - линейный.
5. Можете вы улучшить алгоритм из предыдущего задания, чтобы он был \(O(n\log(n))\)?