Скачать презентацию
Идет загрузка презентации. Пожалуйста, подождите
Презентация была опубликована 10 лет назад пользователемАлина Яшутина
1 Применение деревьев для представления строковой информации Абдрашитов Д. С. (гр. 6538) Руководитель Корнеев Г. А., к.т.н., доцент кафедры КТ
2 2 Применение деревьев для представления строковой информации Операции со строками Получение длины Получение подстроки Получение символа Конкатенация Вставка Удаление Замена
3 3 Применение деревьев для представления строковой информации Существующие методы ОперацияЧасть строки Изменяемые строки Неизменяемые строки Циклические очереди Двусвязные списки Функциональные строки Получение подстроки O(m)O(1)O(m)O(n + m) Конкатенация O(n + m) O(m)O(1)O(n) ИндексацияконцыO(1) серединаO(1) O(n) Вставка символа началоO(n) O(1) серединаO(n) конецO(1)O(n)O(1) O(n) Удаление символа началоO(n)O(1) серединаO(n) конецO(1) O(n) Замена символаO(1)O(n)O(1)O(n)
4 4 Применение деревьев для представления строковой информации Конкатенация строк Текст1Текст2Текст1Текст2 +=
5 5 Применение деревьев для представления строковой информации Конкатенация связок Текст1Текст2 Текст1Текст2 += +
6 6 Применение деревьев для представления строковой информации Пример связки СПбГУ + ИТМО +
7 7 Применение деревьев для представления строковой информации Связки с буферами префикссуффикс середина Связка Стек 0 … log n ~n
8 8 Применение деревьев для представления строковой информации Связки реального времени Связки Стек log n … 2 log n~nlog n … 2 log nlog n
9 9 Применение деревьев для представления строковой информации Сравнение оценок времени ОперацияЧасть строкиНеизменяемые строкиСвязки с буферамиФункциональные деки реального времени с конкатенацией Получение подстрокиконцыO(1)O(min(m, log n))O(m) серединаO(1)O(log n)н/дн/д КонкатенацияO(n + m)O(min(m, log n))O(1) ИтерированиеO(1) ИндексацияконцыO(1) серединаO(1)O(log n)н/д Вставка символаконцыO(n)O(1) серединаO(n)O(log n)н/д Удаление символаконцыO(1) серединаO(n)O(log n)н/д Замена символа на символконцыO(n)O(1) серединаO(n)O(log n)н/д Вставка строкиконцыO(n + m)O(min(m, log n))O(1) серединаO(n + m)O(log n)н/д
10 10 Применение деревьев для представления строковой информации Практическая реализация Замена класса String сбалансированными связками с использованием декартовых деревьев Замена класса StringBuilder с использованием идеи буферов логарифмического размера
11 11 Применение деревьев для представления строковой информации Результаты эксперимента Суммарное время Стандартные строки: 405 сек Сбалансированные связки: 647 сек Время без индексации Стандартные строки: 301 сек Сбалансированные связки: 286 сек
12 12 Применение деревьев для представления строковой информации Полученные результаты Метод представления строк с амортизированными оценками Метод представления строк с гарантированными оценками Хронологическая структура данных для деков с операцией конкатенации
13 13 Применение деревьев для представления строковой информации Благодарю за внимание
Еще похожие презентации в нашем архиве:
© 2024 MyShared Inc.
All rights reserved.