Deque - сложность произвольного доступа

@GoldenId · Регистрация: 11.11.2010

Студворк — интернет-сервис помощи студентам

Тут написано:

Сложность (производительность) стандартных операций над двусторонней очередью следующая:

Произвольный доступ - постоянная O(1)

как так? Я привык считать, что дек - хранится двусвязным списком....

@GbaLog- · 06.09.2017, 19:42

возможно, стоит подучить, что такое сложность алгоритма.

oldnewyear · 07.09.2017, 00:45

Сообщение от GoldenId

Тут написано:

как так? Я привык считать, что дек - хранится двусвязным списком....

По ссылке написано, что в данном случае дек реализован как индексированный набор массивов

Croessmah · 08.09.2017, 09:46

Сообщение от GoldenId

как так?

Да прям "в лоб":

C++
1
2
3
4
value_type &operator[](size_t index)
{
    return *(chunks[index / chunk_size] + index % chunk_size);
}

Новые блоги и статьи Все статьи Все блоги /
Деплой Flask приложения py-thonny 23.06.2025 За годы работы с Flask я натыкался на одни и те же грабли достаточно часто, чтобы наконец научится их обходить. И сегодня хочу поделится опытом, который сбережет вам немало нервных клеток. Начнем с. . .	WebAssembly и контейнеры в .NET Aspire для оркестрации распределенных архитектур ArchitectMsa 23.06.2025 Я наблюдаю, как WebAssembly (или просто WASM) постепенно выходит за рамки своего первоначального предназначения — исполнения кода на стороне браузера. Теперь эта технология проникает в серверную. . .	Непрерывная интеграция для пакета Python Mr. Docker 22.06.2025 Было 4 часа утра пятницы, когда я выпустил новую версию нашей внутренней библиотеки для обработки данных. Релиз 0. 5. 2 содержал небольшой фикс для обработки дат в ISO формате, что может пойти не так?. . .	Продвинутый ETL на C# из OLTP БД в хранилище stackOverflow 22.06.2025 Работая в сфере корпоративной аналитики, я постоянно сталкиваюсь с одним и тем же - нужны чистые, структурированные и, главное, свежие данные. Без них современные аналитические системы, машинное. . .	Мастер-класс по микросервисам на Node.js Reangularity 21.06.2025 Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .
Управление Arduino из WPF приложения Wired 21.06.2025 Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .	Звёздная пыль kumehtar 20.06.2025 Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .	Создание нейросети с PyTorch AI_Generated 19.06.2025 Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .	JWT аутентификация в ASP.NET Core UnmanagedCoder 18.06.2025 Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .	Краткий курс по С# aaLeXAA 18.06.2025 Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .

@GbaLog- Любитель чаепитий 3744 / 1800 / 566 Регистрация: 24.08.2014 Сообщений: 6,018 Записей в блоге: 1
	06.09.2017, 19:42
	возможно, стоит подучить, что такое сложность алгоритма. 0

Опции темы