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

19
Проблемы, которые доказуемо требуют квадратичного времени

Я ищу примеры проблемы, которая имеет нижнюю границу ) для входа x .Ω ( | x |2Ω(|x|2\Omega(|x|^2Иксxx Проблема должна иметь следующие свойства: доказательство времени выполнения для любого алгоритма - первым приоритетом должен быть как можно более простой аргумент нижней границы.Ω (...

18
Умное управление памятью с постоянными операциями времени?

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

18
Эффективные алгоритмы для задачи вертикальной видимости

Размышляя над одной проблемой, я понял, что мне нужно создать эффективный алгоритм, решающий следующую задачу: Проблема: нам дан двумерный квадратный прямоугольник со стороной nnn , стороны которого параллельны осям. Мы можем посмотреть на это через верх. Тем не менее, есть также mmm горизонтальных...

18
Почему циклы быстрее, чем рекурсия?

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

17
Почему факторинг больших целых чисел считается трудным?

Я прочитал где - то , что наиболее эффективный алгоритм найден можно вычислить факторы в O ( exp( ( 64 / 9 ⋅ б )1 / 3⋅ ( журналb)2/3)O(exp⁡((64/9⋅b)1/3⋅(log⁡b)2/3)O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3}) время, но код я написал это или возможно зависимости от того, насколько быстры деление...

16
Плотный NP полный язык подразумевает P = NP

Мы говорим, что язык является плотным, если существует такой многочлен , что для всехДругими словами, для любой заданной длины существует только многочлен много слов длины , которых нет вJ⊆ Е*J⊆Σ*J \subseteq \Sigma^{*}| J c ∩ Σ n | ≤ р ( п ) п ∈ N . п п J .ппp| Jс∩ ЕN| ≤p(n)|Jс∩ΣN|≤п(N) |J^c \cap...

16
Сложный алгоритм триангуляции Делоне.

В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены...

15
Где ошибка в этом, очевидно, -O (n lg n) алгоритме умножения?

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

15
Почему бы не взять одинарное представление чисел в числовых алгоритмах?

Алгоритм псевдополиномиального времени - это алгоритм, который имеет полиномиальное время работы на входном значении (величина), но экспоненциальное время работы на входном размере (количество бит). Например, для проверки, является ли число простым или нет, требуется выполнить цикл по числам от 2...

14
Нахождение максимального XOR двух чисел в интервале: можем ли мы сделать лучше, чем квадратичное?

Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby ​​у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...

14
Установить сходство - вычислить индекс Жакара без квадратичной сложности

У меня есть группа из n наборов, для которых мне нужно вычислить значение типа «уникальность» или «сходство». Я остановился на индексе Жакара как на подходящей метрике. К сожалению, индекс Жакара работает только с двумя наборами одновременно. Для того чтобы вычислить сходство между всеми...

14
Существует ли эффективный алгоритм эквивалентности выражений?

например, ?xy+x+y=x+y(x+1)xy+x+y=x+y(x+1)xy+x+y=x+y(x+1) Выражения взяты из обычной школьной алгебры, но ограничены арифметическим сложением и умножением (например, ), без инверсий, вычитания или деления. Буквы являются переменными.2+2=4;2.3=62+2=4;2.3=62+2=4; 2.3=6 Если это поможет, мы можем...

14
Сложность вычислительных матриц

Я заинтересован в вычислении nNn «ю мощность матрицы . Предположим, у нас есть алгоритм умножения матриц, который выполняется за время . Тогда можно легко вычислить за время. Можно ли решить эту проблему за меньшее время?n×nN×Nn\times...

14
Алгоритм БПФ для попарных сумм

Предположим, что нам дано различных целых чисел , таких что для некоторой константы и для всех .a 1 , a 2 , … , a n 0 ≤ a i ≤ k n k > 0 innna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iяi Нас интересует нахождение отсчетов всех возможных попарных сумм...

14
Границы времени выполнения разрешимы для чего-нибудь нетривиального?

Задача   Дана машина Тьюринга которая знает время выполнения O ( g ( n ) ) относительно длины ввода n , является временем выполнения M ∈ O ( f ( n ) )MMMO (г( н ) )О(грамм(N)){O}(g(n))NNnM∈ O ( f( н ) )M∈О(е(N))M \in {O}(f(n)) ? Разрешима ли указанная выше проблема для некоторых нетривиальных пар...

14
Нахождение пятиконечной звезды за полиномиальное время

Я хочу доказать, что это часть моей домашней работы по курсу, который я сейчас прохожу. Я ищу некоторую помощь в продолжении, а не ответ. Это вопрос, о котором идет речь: 5-точечная звезда в неориентированном графе является 5-кликой. Покажите, что 5-POINTED-STAR , где 5-POINTED-STAR = содержит...

14
Пространственно-временное решение проблемы пропущенного элемента

Здесь известная проблема. Для массива A[1…n]A[1…n]A[1\dots n] натуральных чисел выведите наименьшее натуральное число, которого нет в массиве. Проблема может быть решена в O(n)O(n)O(n) пространстве и времени: прочитать массив, отслеживать в O(n)O(n)O(n) пространстве, произошло ли...

14
Разница между сложностью времени и вычислительной сложностью

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

13
Временная сложность тройного вложенного цикла

Пожалуйста, рассмотрите следующую тройную вложенную петлю: for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) for (int k = j; k <= n; ++k) // statement Здесь утверждение выполняется ровно раз Может кто-нибудь объяснить, как эта формула была получена?...