Упражнения

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