Понедельник, 21.09.2020, 14:40
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2019 » Октябрь » 31 » Алгоритмы и структуры данных на C++: деревья отрезков
19:25
Алгоритмы и структуры данных на C++: деревья отрезков

Алгоритмы и структуры данных на C++: деревья отрезков

Вкратце о том, что из себя представляет задача на запрос по диапазону: дан массив a из n элементов, дано кол-во запросов q. Для каждого запроса даны границы l, r такие, что 1 ≤ l ≤ r ≤ n.

Требуется для каждого запроса найти максимум/минимум/сумму/НОД и проч. среди элементов a(l), a(l + 1) … a(r - 1), a(r).

Предположим, мы имеем массив длины n = 105 и кол-во запросов q = 105. Если искать максимум/сумму и проч. в массиве «наивным» методом, асимптотическая сложность которого O(n), в задаче на обработку запросов мы будем иметь сложность O(nq), что в данном случае – 1010. При том, что современные ЭВМ обрабатывают 108 о/с, данное решение не является оптимальным.

Просмотров: 132 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Октябрь 2019  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2020