Постоянные структуры данных являются неизменными структурами данных. Операции над ними возвращают новую «копию» структуры данных, но измененную операцией; старая структура данных остается неизменной. Эффективность обычно достигается за счет совместного использования некоторых базовых данных и...
Динамические деревья играют важную роль в решении таких проблем, как сетевые потоки, динамические графы, комбинаторные задачи («Динамические деревья на практике» Тарьяна и Вернека) и недавно объединенные словари («Простой объединяемый словарь» Адама Карчмара), Под динамическими деревьями я ссылаюсь...
У меня есть массив из 100 000 строк, все длиной kkk . Я хочу сравнить каждую строку с любой другой строкой, чтобы увидеть, отличаются ли любые две строки на 1 символ. Прямо сейчас, когда я добавляю каждую строку в массив, я проверяю ее по каждой строке, уже находящейся в массиве, которая имеет...
Размышляя над одной проблемой, я понял, что мне нужно создать эффективный алгоритм, решающий следующую задачу: Проблема: нам дан двумерный квадратный прямоугольник со стороной nnn , стороны которого параллельны осям. Мы можем посмотреть на это через верх. Тем не менее, есть также mmm горизонтальных...
Из ответов на (Когда) есть поиск в хэш-таблице O (1)? Я понимаю, что хеш-таблицы имеют O ( 1 )О(1)O(1) наихудшее поведение, по крайней мере амортизированное, когда данные удовлетворяют определенным статистическим условиям, и существуют методы, которые помогут сделать эти условия широкими. Однако, с...
У меня есть небольшой исторический вопрос, а именно, как следует из заголовка, я ищу раннее использование деревьев (в качестве структуры данных, дерева поиска и т. Д.) В компьютерной...
Я думал, что ассоциативный массив (т. Е. Карта или словарь) и таблица хеширования были одним и тем же понятием, пока я не увидел в Википедии, что Для словарей с очень небольшим количеством привязок может иметь смысл реализовать словарь, используя список ассоциаций, связанный список привязок. ......
В моем курсе « Алгоритмы и структуры данных» профессора, слайды и книга ( Введение в алгоритмы, 3-е издание ) использовали слово NILдля обозначения, например, дочернего элемента узла (в дереве), который не существует. Однажды, во время лекции, вместо того, чтобы сказать NIL, мой одноклассник сказал...
У меня есть несколько объектов с приоритетом, который является составным типом и только частично упорядочен . Мне нужно выбрать объекты в порядке приоритета (т.е. каждый раз приносить минимальный предмет). Но вместо того, чтобы произвольно завершать порядок, я бы предпочел, чтобы очередь была...
Рассмотрим следующий вопрос Google Code Jam в 1С : Великая китайская стена начинается бесконечной линией, где высота во всех местах равна .000 Некоторое количество племен , , будет атаковать стену в соответствии со следующими параметрами - начальный день, , начальная сила , начальная западная...
Я пытаюсь доказать, что двоичная куча с узлами имеет точно exactly nnnnвыходит, учитывая, что куча строится следующим образом:⌈n2⌉⌈n2⌉\left\lceil \frac{n}{2} \right\rceil Каждый новый узел вставляется через percolate up . Это означает, что каждый новый узел должен быть создан на следующем доступном...
Во многих обсуждениях двоичной кучи в качестве поддерживаемой операции для минимальной кучи обычно указывается только ключ уменьшения. Например, глава 6.1 CLR и эта страница википедии . Почему ключ увеличения обычно не указывается для min-heap? Я полагаю, что это можно сделать в O (высота),...
Я заметил, что при реализации поисковых алгоритмов используются разные структуры данных. Например, мы используем очереди для реализации поиска в ширину, стеки для поиска в глубину и мини-кучи для реализации алгоритма A * . В этих случаях нам не нужно явно создавать дерево поиска. Но я не могу найти...
Обычный вопрос интервью - дать алгоритм для определения того, является ли данное двоичное дерево сбалансированным по высоте (определение дерева AVL). Мне было интересно, можем ли мы сделать что-то подобное с красно-черными деревьями. Учитывая произвольное неокрашенное двоичное дерево (с узлами...
Я задал этот вопрос в общем стеке потока, и я был направлен сюда. Было бы хорошо, если бы кто-нибудь мог объяснить, как подходить к частичным или полностью динамическим задачам с графами в целом. Например: Найти кратчайший путь между двумя вершинами в неориентированном взвешенном графе для...
Я хочу начать с того, что это НЕ домашний вопрос. Я читаю Введение в алгоритмы - известный текст CLRS, чтобы стать лучшим программистом. Я пытаюсь решить проблемы и упражнения, приведенные в книге, самостоятельно. Я пытаюсь решить Excercise 10.1-2 из главы 10 «Элементарные структуры данных» из...
Я столкнулся с алгоритмом, чтобы решить реальную проблему, и я помню класс, который я взял, где я сделал что-то очень похожее для некоторых для домашней работы. По сути, это график точек, и линии нарисованы так, чтобы они были равноудалены между двумя точками. Он образует идеальное разделение, где...
Мне сказали, что мы будем использовать список, если граф разреженный, и матрицу, если граф плотный . Для меня это просто грубое определение. Я не вижу многого за этим. Можете ли вы уточнить, когда это будет естественным выбором? Заранее...
Размещая геометрические объекты в квадри (или октодереве), вы можете разместить объекты, размер которых превышает один узел, несколькими способами: Размещение ссылки на объект в каждом листе, для которого он содержится Размещение ссылки на объект в самом глубоком узле, для которого он полностью...
У меня есть два больших наборов целых чисел AAA и . Каждый набор содержит около миллиона записей, и каждая запись представляет собой положительное целое число длиной не более 10 цифр. BBB Каков наилучший алгоритм для вычисления и ? Другими словами, как я могу эффективно вычислить список записей ,...