Различия между версиями 4 и 5
⇤ ← Версия 4 от 2011-05-04 16:29:09 →
Размер: 1342
Редактор: FrBrGeorge
Комментарий:
← Версия 5 от 2011-05-04 16:38:31 → ⇥
Размер: 1884
Редактор: FrBrGeorge
Комментарий:
Удаления помечены так. Добавления помечены так.
Строка 17: Строка 17:
   * виды деревьев AVL, красно-чёрное, декартовы
Строка 22: Строка 23:
  1. Второе   1. Сгенерировать таблицу вида [уникальное случайное число, случайная строка] на 10**5 элементов. Измерить время поиска элемента по 1000 поисковых проб в этих данных, представленных в виде
   1. Списка
   1. хешированной таблицы
   1. дерева
   1. стандартного словаря
  1.

Тема занятия: структуры данных и поиск

  • {o} — тема по Linux

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

  • массив -- прямой доступ
  • список -- ассоциативный доступ

  • хеш-таблицы, функция hash(), реализация словарей

  • Полиномиальное хеширование
    • H=(a0*p**0+a1*p**1+...+an*p**n)%2**16, где p -- простое число, например, 31337
  • Дерево бинарного поиска [значение,поддерево-меньше, поддерево-больше]
    • оптимальное дерево: размер(поддерево-меньше)~=размер(поддерево-больше)
    • заполнение дерева с перебалансировкой
      • виды деревьев AVL, красно-чёрное, декартовы

    • дерево в общем виде [значение,поддерево-<K1,поддерево-K1<k2,...,поддерево-kn-1<kn,поддерево->kn)]

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

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

  • {*} — новая тема

  1. {i} Первое

  2. Сгенерировать таблицу вида [уникальное случайное число, случайная строка] на 10**5 элементов. Измерить время поиска элемента по 1000 поисковых проб в этих данных, представленных в виде
    1. Списка
    2. хешированной таблицы
    3. дерева
    4. стандартного словаря

CategoryClass CategoryVmsh

LecturesVMSH/2011-05-04 (последним исправлял пользователь FrBrGeorge 2011-05-11 14:52:26)