Я много раз встречал этот термин в различных учебных материалах по КС: L2 CS162 (Калифорнийский университет в Беркли): Отображение в памяти ввода-вывода L4 CS162 (Калифорнийский университет в Беркли): Файлы с отображенной памятью L24 CS61 (UC Berkeley): «Операции ввода-вывода с отображением в...
Мне нужно сохранить коллекцию целых чисел в диапазоне от 0 до 65535, чтобы я мог быстро сделать следующее: Вставьте новое целое число Вставьте диапазон смежных целых чисел Удалить целое число Удалить все целые числа ниже целого Проверьте, присутствует ли целое число У моих данных есть свойство...
Для данного плоского графа встроены в плоскости, определяется набором отрезков Е = { е 1 , . , , , e m } , каждый сегмент e i представлен своими конечными точками { L i , R i } . Создайте структуру данных DCEL для плоского подразделения, опишите алгоритм, докажите его правильность и покажите...
Я запутался, решая следующую проблему (вопросы 1–3). Вопрос Д -ичные куч, как двоичные кучи, но (с одним возможным исключением) узлы без листьев имеют d детей вместо 2 -х детей. Как бы вы представили d -ary кучу в массиве? Какова высота d- дневной кучи из n элементов в терминах n и d ? Дайте...
Я понимаю , что сегментные дерева могут быть использованы , чтобы найти сумму юга массива . И что это может быть сделано за O ( log n ) в соответствии с руководством здесь .AAAO(logn)O(logn)\mathcal{O}(\log n) Однако я не могу доказать, что время запроса действительно равно . Эта ссылка (и многие...
Я пытаюсь понять, как двоичные индексированные деревья (деревья Фенвика) могут быть изменены для обработки как запросов диапазона, так и обновлений диапазона. Я нашел следующие источники: http://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/...
В моем классе Java мы изучаем сложность различных типов коллекций. Вскоре мы будем обсуждать бинарные деревья, о которых я читал. Книга утверждает, что минимальная высота бинарного дерева составляет , но не дает дополнительных объяснений.log2(n+1)−1log2(n+1)−1\log_2(n+1) - 1 Может кто-нибудь...
Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )nnnO(logn)O(logn)O(\log...
Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E | )[1,…,K][1,…,K][1,\dots,...
Рандомизированные связываемые кучи имеют операцию «соединение», которую мы затем используем для определения всех других операций, включая вставку. Вопрос в том, какова ожидаемая высота этого дерева с узлами?nnn Теорема 1 Гамбина и Малинковского « Рандомизированные смешиваемые приоритетные очереди»...
Я хочу эффективно отфильтровать список целых чисел для дубликатов таким образом, чтобы хранить только полученный набор. Один способ это можно увидеть: у нас есть диапазон целых чисел с N большим (скажем, 2 40 )S={1,…,N}S={1,…,N}S = \{1, \dots{}, N\}NNN2402402^{40} у нас есть функция с,...
Я изучаю методы реализации языков программирования и недавно натолкнулся на стеки спагетти, которые предположительно хорошо подходят для модели стиля передачи продолжения (учитывая их использование, например, в Scheme и SML / NJ ). Для упрощения, давайте рассмотрим только однопоточные процессы для...
Хотя я работаю программистом в своей повседневной жизни и использую все модные языки (Python, Java, C и т. Д.), У меня все еще нет четкого представления о том, что такое функциональное программирование. Из того, что я прочитал, одно свойство функциональных языков состоит в том, что структуры данных...
Скажем, у меня есть неориентированный конечный разреженный граф, и мне нужно эффективно выполнять следующие запросы: IsConnected(N1,N2)IsConnected(N1,N2)IsConnected(N_1, N_2) - возвращает если есть путь между и N_2 , в противном случае FН 1 Н 2 FTTTN1N1N_1N2N2N_2FFF...
У меня есть подмножество простых путей в графе. Длина путей ограничена .ddd Каким самым компактным способом (с точки зрения памяти) я могу представить пути так, чтобы не были представлены никакие другие пути, кроме выбранных? Обратите внимание, что я хочу использовать это представление в алгоритме,...
Я ищу реализацию заданного типа данных. То есть мы должны поддерживать динамическое подмножество SSS (размера nnn ) из юниверса U={0,1,2,3,…,u–1}U={0,1,2,3,…,u–1}U = \{0, 1, 2, 3, \dots , u – 1\} размера uuu с операции insert(x)(добавить элемент xв SSS ) и find(x)(проверяет, xявляется ли элемент...
При вставке элемента в дерево сопряжения повороты выполняются парами на основе зигзагообразного или зигзагообразного рисунка. Когда нужно выполнить нечетное количество поворотов, можно либо сделать дополнительное вращение, начиная с листа, либо сохранить дополнительное вращение и сделать это в...
SkipList предоставляет те же границы для поиска, что и сбалансированное дерево, с тем преимуществом, что перебалансировка не требуется. Поскольку SkipList создается с использованием случайных бросков монет, эти границы сохраняются только до тех пор, пока структура SkipList достаточно...