Вопросы с тегом «time-complexity»

Обычно в алгоритмах мы не заботимся о сравнении, сложении или вычитании чисел - мы предполагаем, что они выполняются за время . Например, мы предполагаем это, когда говорим, что сортировка на основе сравнения - это O ( n log n ) , но когда числа слишком велики, чтобы поместиться в регистры, мы...

Я считаю, что у меня есть разумное представление о сложностях, таких как , Θ ( n ) и Θ ( n 2 )O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) . С точки зрения списка, - это постоянный поиск, поэтому он просто получает заголовок списка. Θ ( n ) - это место, где я прошёл бы весь список,...

Я сталкивался со многими алгоритмами сортировки во время учебы в старшей школе. Тем не менее, я никогда не знаю, какой самый быстрый (для случайного массива целых чисел). Итак, мои вопросы: Какой самый быстрый в настоящее время известный алгоритм сортировки? Теоретически, возможно, что есть еще...

Чтобы найти медиану несортированного массива, мы можем сделать минимальную кучу за времени для элементов, а затем мы можем извлечь один за другим элементов, чтобы получить медиану. Но этот подход занял бы времени.O(nlogn)O(nlog⁡n)O(n\log n)nnnn/2n/2n/2O(nlogn)O(nlog⁡n)O(n \log n) Можем ли мы...

Я ищу структуру данных , которая хранит множество строк над набором символов , способных выполнять следующие операции. Обозначим через D ( S ) в качестве структуры данных , хранящей множество строк S .ΣΣ\SigmaD(S)D(S)\mathcal{D}(S)SSS Add-Prefix-Setна : для некоторого множества T (возможно, пустых)...

Какова временная сложность нахождения диаметра графа ?G = ( V, E)G=(V,E)G=(V,E) O ( | V|2)O(|V|2){O}(|V|^2) O ( | V|2+ | В| ⋅ | Е| )O(|V|2+|V|⋅|E|){O}(|V|^2+|V| \cdot |E|) O ( | V|2⋅ | Е| )O(|V|2⋅|E|){O}(|V|^2\cdot |E|) O ( | V| ⋅ | Е|2)O(|V|⋅|E|2){O}(|V|\cdot |E|^2) Диаметр графа является...

Существует ли структура данных для ведения упорядоченного списка, которая поддерживает следующие операции за время амортизации ?O ( 1 )O(1)O(1) GetElement (k) : возвращает й элемент списка.Кkk InsertAfter (x, y) : вставить новый элемент y в список сразу после x. Удалить (x) : удалить x из списка....

Учитывая любую вычислительную проблему, является ли задача нахождения нижних границ для такого вычисления действительно возможной? Я полагаю, что все сводится к тому, как определяется один вычислительный шаг и какую модель мы используем для доказательства, но, учитывая это, действительно ли мы...

Я изучаю C ++ и заметил, что время выполнения функции push_back для векторов постоянно «амортизируется». В документации также отмечается, что «если происходит перераспределение, само перераспределение будет линейным во всем размере». Разве это не означает, что функция push_back - это , где - длина...

Так что я понимаю идею, что решение проблемы определяется как Есть ли путь P такой, что стоимость ниже, чем C? и вы можете легко проверить это, проверив полученный вами путь. Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с...

Название устанавливает вопрос. В качестве входных данных у нас есть список элементов, которые мы можем сравнить (определить, какой из них больше ). Ни один элемент не может быть равным. Ключевые моменты: Сравнение не является транзитивным (подумайте о бумажных ножницах): это может быть правдой:...

Некоторые сложные алгоритмы ( объединение-поиск ) имеют почти постоянную обратную функцию Аккермана, которая появляется при асимптотической сложности времени, и являются оптимальными по времени в худшем случае, если почти постоянный обратный член Аккермана игнорируется. Существуют ли примеры...

Интересно, как найти обхват разреженного неориентированного графа. Под редким я подразумеваю . Под оптимальным я подразумеваю минимальную временную сложность.| Е| =O( | V| )|E|=O(|V|)|E|=O(|V|) Я думал о некоторой модификации алгоритма Тарьяна для неориентированных графов, но я не нашел хороших...

Я столкнулся со следующими сомнениями в сложности Ханойских башен , на которые мне хотелось бы получить ваши комментарии. Это в НП? Попытка ответа: предположим, что Пегги (проверяющий) решает проблему и передает ее Виктору (проверяющему). Виктор может легко увидеть, что окончательное состояние...

В последнее время я немного читал литературу и нашел довольно интересные структуры данных. Я исследовал различные методы уменьшения времени обновления до худшем случае [1-7].O ( 1 )О(1)\mathcal{O}(1) Недавно я начал изучать структуры данных без блокировок для поддержки эффективного параллельного...

Просто ради интереса я попытался решить проблему из категории «Недавние» Project Euler ( последовательность цифр суммы ). Но я не могу придумать, как решить проблему эффективно. Проблема заключается в следующем (в исходной последовательности вопросов в начале есть две, но она не меняет...

Предположим , что мы имеем ориентированный граф и два узла A и B . Я хотел бы знать, есть ли уже алгоритмы для расчета следующей задачи решения:G = ( V, E)G=(V,E)G=(V,E)AAAВBB Есть ли хотя бы два пути между и В одинаковой длины?AAAВBB Как насчет сложности? Могу ли я решить это за полиномиальное...

Дискретный логарифм такого же , как нахождение в , дан в , гр и N .bbba c Nab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Интересно, в каких группах сложности (например, для классических и квантовых компьютеров) это находится, и какие подходы (то есть алгоритмы) являются лучшими для выполнения этой задачи....

В статье Рамирес-Альфонсон « Сложность проблемы Фробениуса» доказана, что задача NP-полна с использованием редукций Тьюринга. Это возможно? Как именно? Я думал, что это было возможно только за полиномиальное время много одного сокращения. Есть ли какие-либо ссылки по этому поводу? Существуют ли два...

Поскольку существует только константа между основаниями логарифмов, не так ли просто написать f(n)=Ω(logn)f(n)=Ω(log⁡n)f(n) = \Omega(\log{n}) , в отличие от Ω(log2n)Ω(log2⁡n)\Omega(\log_2{n}) , или какова бы ни была...