Презентация на тему "Лабиринтики и quickunion"

Содержание

• 
  Слайд 1

  Лабиринтики и quickunion

• 
  Слайд 2

  ПРОСЫПАЕМСЯ!!!

  Сколько связанных компонент можно получить при выполнении следующей последовательности команд union на наборе из 10 элементов? 1-2; 3-4; 5-6; 7-8; 7-9; 2-8; 0-5; 1-9 Варианты:решение: 1 2 3

• 
  Слайд 3
  

  Какое максимальное числоэлементов массива id[] может быть изменено при выполнении одной команды union когда мы используем quick-find, а размер массива N? Варианты: 1 LgN N-1

• 
  Слайд 4
  

  Есть структура данных quick-union из 10 элементов и их id[] соответственно равны 0 9 6 5 4 2 6 1 0 5 Чему равны корни 3 и 7, соответственно? Варианты: 3 и 7 4 и 4 6 и 4 6 и 6

• 
  Слайд 5
  

  Каким может быть максимальное число запросов к массиву во время операции поиска (connected)для алгоритма Quick-union от числа элементов N в массиве Варианты: постоянно логарифмично Линейно

• 
  Слайд 6
  

  Дан массив id[] для WQU алгоритма Какой id[] изменится при выполнении операции Union(3,6) Варианты: ID[0] ID[3] ID[6] ID[8]

• 
  Слайд 7

  Ответ

  Ответ – id[8]. Так как сравниваем алгоритмы по числу элементов, а не по высоте. У дерева с 0 вес ~ 6, a у дерева 8 вес ~ 4. По правилу присоединяем меньшее дерево к большему, сравнивая по весу => меняется id[8]

• 
  Слайд 8

  Вопрос для суперигры

  Когда открывается новый узел, сколько раз вызывается команда UNION()? Варианты: 0,1,2,3 или 4

• 
  Слайд 9

  Анализ алгоритмов

• 
  Слайд 10

  ПРОСЫПАЕМСЯ!

  Дано: N = 1,000,000 (1 миллион) Во сколько быстрее работает алгоритм N*log2N по сравнению с N2? в 20 в 1000 в 50,000

• 
  Слайд 11

  Просыпаемся

  Вы измеряете время работы программыT(N) (сек), как функции размера входных данных N. Какая из этих функций лучше всего описывает время работы. 3.3 * 10-4 * N N2 5.0 * 10-9 * N2

• 
  Слайд 12

  Просыпаемся!

  Сколько обращений к массиву происходит в следующем фрагменте кода? 12

• 
  Слайд 13

  Ответ

  Не все тройные циклы работают за кубическое время. В данном случае в цикл с параметром k работает 3lgN раз, вместо N раз, так как каждую итерацию k увеличивается вдвое. Первые 2 цикла работают по N раз каждый Итого 3/2 * N * N * lgN

• 
  Слайд 14

  Просыпаемся!

  Чему равно максимальное число обращений к массиву в алгоритме бинарного поиска в отсортированном массиведлины N Постоянно Логарифмично

• 
  Слайд 15
  

  Какая из следующих функций O(N3)? 15

• 
  Слайд 16

  Ответ

  O() определяет верхнюю границу роста функции, кубичность характерна для них всех.

• 
  Слайд 17

  Просыпаемся!

  Сколько памяти (в байтах) использует взвешенный QuickUnionUFсостоящий из массива в N элементов? Hint: 2 integer arrays size of N 17 Вещественное число (int) занимаетв памяти 4 байта Если массив состоит из N веществ чисел, то занимает 4*N байт памяти В QuickUnionнаходится 2 целочисленных массива значит он занимает ~ 8N байт

• 
  Слайд 18

  Стеки и очереди

• 
  Слайд 19

  Просыпаемся!

  Какой из следующих входных данных в стек не сможет воспроизвести следующий вывод на экран: 5 4 3 2 1 Варианты: 1 2 3 4 5 - - - - - 1 2 5 - 3 4 - - - - 5 - 1 2 3 -4 - - -

• 
  Слайд 20
  

  Дана ссылка first, ссылающаяся на 1ый элемент стека (реализация с пом списка связанных элементов), в котором минимум 2 элемента, что делает представленный код? Удаляет первый элемент в стеке Удаляет второй элемент стека Удаляет предпоследний элемент стека Удаляет последний элемент в стеке

• 
  Слайд 21

  Ответ

  X.next.next!= null –проверяет, не является ли следующий за ним элемент последним в стеке. Так как если a.next == null, то он последний, так как уже ни на что не указывает. Соответственно, как только предпоследний элемент достигается по проходу цикла, условие в while уже не выполняется и происходит выход из цикла. После которого следующий за предпоследним элемент, то есть последний, удаляется (зануляется).

• 
  Слайд 22

  Просыпаемся!

  Предположим, что начиная с пустой структуры, мы производим Npush() операций в стеке, реализованном на основе массива изменяемого размера.Как будет вызываться метод resize()? Постоянно Логарифмично

• 
  Слайд 23

  Сортировка

• 
  Слайд 24

  ПРОСЫПАЕМСЯ!

  Число сравнений для уже отсортированного входного массива алгоритма сортировки с выбором… Линейно Квадратично

• 
  Слайд 25

  Просыпаемся

  Число сравнений для уже отсортированного массива для метода сортировки с вставкой… Постоянно Логарифмично Линейно

• 
  Слайд 26

  ПРОСЫПАЕМСЯ!

  Число сравнений для уже отсортированного массива для метода сортировки Шелла при инкременте 3x+1… Постоянно Логарифмично Линейно N*logN

• 
  Слайд 27

  Просыпаемся!

  Каково максимальное число раздач 52 карт? 52! На предыдущем слайде ответ

• 
  Слайд 28
  

  Максимальное число вершин на выпуклой оболочке для множества из N точек… Постоянно Логарифмично Линейно