Структуры данных (18 сентября 2024)


  1. [30 минут] Амортизированое время работы
    1. На операцию (real time) ti, в среднем (average time) mi = (sum ti) / n, амортизированное ai = ti + Δφ
    2. Теорема о связи амортизированного и среднего времени
    3. Примеры на амортизированное время (amortized time)
      1. Пример с вектором
      2. Пример со стеком PUSH, POP_K
      3. Пример a2 + b2 = N : правильный потенциал = b
      4. Пример a2 + b2 = N : пример неправильного потенциала, b2
    4. Амортизация монетками, определение и равносильность.

  2. [20 минут] Бинпоиск
    1. Сортированный массив: sort(a, a+n)
    2. Поиск позиции x в сортированном массиве. 3 ветки: x.
    3. lower_bound (первый >= x) и upper_bound (первый >x),
    4. Правильный бинпоиск: по инварианту. В l выполняется, в r не выполняется, r-l>1.
    5. Вещественный бинпоиск. Поиск корня многочлена нечётной степени.
− Перерыв −
  1. [15 минут] Два указателя + сортированный массив
    1. Online решение : sort + bs (задача: поиск всех элементов массива B в массиве A)
    2. Offline решение : sort + sort + два указателя
    3. Пересечение множеств (и мультимножеств!), C++ set_intersection. Пишем две версии кода: while и for.
    4. Ещё задачи на два указателя и множества: merge, union, set_difference.

  2. [30 минут] Хеш-таблица
    1. Введение: зачем это надо, что мы делаем.
      1. Задача: для каждого x помнить, сколько раз он встречается. Если x=1..106, просто массив. А если x до 109? unordered_map
      2. Другая задача. Множество с операциями: добавить, удалить, проверить, есть ли элемент. Если x=1..106, просто массив. А если x до 109? unordered_set
    2. HashSet на списках: vector<int> h[M]; hash(x), vecor::push_back, vector::find
    3. Как выбрать функцию hash? Самая простая hash(x) = x % M
    4. C++ : unordered_set<int> s(N), unordered_map<int,int> m(N), MyHash { size_t operator() ( T t ); }
    5. Умеем Add, Del, Find. Интерфейсы HashSet, HashMap. Решение задачи про два указателя хеш-таблицей.
    6. Открытая адресация: i = hash(x), while (h[i] && h[i] != x) i++;
    7. Сравнение открытой и списков: открытая быстрее, из списков проще удалять. Удаление из открытой: просто помечаем, когда помеченных слишком много, перестроим таблицу.