Асимптотический анализ пространства, необходимого для запуска алгоритмов.
Мы знаем , что в N L по Иммерман-Szelepcsenyi теорема теорема и так ы т - с O п п е с т я v я т у есть N L - h a r d, следовательно, s t - n
Здесь известная проблема. Для массива A[1…n]A[1…n]A[1\dots n] натуральных чисел выведите наименьшее натуральное число, которого нет в массиве. Проблема может быть решена в O(n)O(n)O(n) пространстве и времени: прочитать массив, отслеживать в O(n)O(n)O(n) пространстве, произошло ли...
Существуют ли известные алгоритмы для сформулированных задач, которые требуют SPACE-сложности O (sqrt (N))? Я знаю, что существуют алгоритмы с такой большой временной...
Учитывая две строки, как вы можете проверить, являются ли они перестановкой друг друга, используя пространство O (1)? Модификация строк никоим образом не допускается. Примечание: O (1) пробел по отношению как к длине строки, так и к размеру...
Существует хорошо известный в худшем случае алгоритм выбора , чтобы найти K «й наибольший элемент в массиве целых чисел. Он использует медиану из-медианы подойти , чтобы найти достаточно хороший стержень, разбивает входной массив на месте , а затем рекурсивно продолжается в его поисках к «го по...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Существуют эффективные структуры данных для представления заданных разделов. Эти структуры данных имеют хорошие временные сложности для таких операций, как Union и Find, но они не особенно эффективны в использовании. Что такое эффективный для пространства способ представления раздела набора? Вот...
У меня есть следующая алгоритмическая проблема: Определить сложность пространства Тьюринга распознавания цепочек ДНК, которые являются палиндромами Уотсона-Крика. Палиндромы Уотсона-Крика - это строки, обратным дополнением которых является исходная строка. Дополнением определяется буква-накрест,...
Я изучал ранговый коэффициент корреляции Спирмена ρ = ∑я( хя- х¯) ( уя- у¯)Σя( хя- х¯)2Σя( уя- у¯)2-------------------√ρзнак равноΣя(Икся-Икс¯)(Yя-Y¯)Σя(Икся-Икс¯)2Σя(Yя-Y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} ....
Доказано, что проблема определения, является ли вход палиндромом или нет, требует пространства на машине Тьюринга. Однако даже для сохранения входных данных требуется пространство n , не значит ли это, что всем машинам Тьюринга требуется пространство Ω ( n ) ?Ω ( журналн )Ω(журналN)\Omega(\log...
На самом деле я обнаружил, что набор контекстно-зависимых языков, ( принятых языков) не так широко обсуждается, как (обычные языки) или (контекстно-свободные языки). А также открытая проблема не так известна, как «аналогичная» проблема: « ".CSLCSL\mathbf{CSL}R E G C F L D S P A C E ( O ( n ) ) = ?...
Поскольку вопрос гласит, как мы можем доказать, что ?NTIME(f(n))⊆DSPACE(f(n))NTIME(f(n))⊆DSPACE(f(n))\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n)) Кто-нибудь может указать мне на доказательство или изложить его здесь?...
Я ищу реализацию заданного типа данных. То есть мы должны поддерживать динамическое подмножество 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является ли элемент...