Описание тега space-complexity
The space complexity of an algorithm quantifies the amount of memory taken by an algorithm to run as a function of the size of the input to the problem. The space complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms.
1
ответ
Пространственно-временная сложность "вложенной" рекурсивной функции
В одном из предыдущих вступительных экзаменов в cs возник вопрос: вычислите пространственную и временную сложность функции f1 как функции от n, предположите, что временная сложность malloc (n) равна O(1), а ее пространственная сложность равна На). i…
26 сен '18 в 14:30
2
ответа
Что такое космическая сложность хвостовой рекурсивной быстрой сортировки?
Глядя на следующий хвостовой рекурсивный псевдокод быстрой сортировки QuickSort(A[1, ..., n], lo, hi) Input: An array A of n distinct integers, the lower index and the higher index // For the first call lo = 1 and hi = n Output: The array A in sorte…
16 окт '18 в 16:08
2
ответа
Пространственная сложность прохождения порядка уровней по очереди
Это код для обхода порядка уровня: public void bfsTraveral() { if (root == null) { throw new NullPointerException("The root cannot be null."); } int currentLevelNodes = 0; int nextLevelNodes = 0; final Queue<TreeNode> queue = new LinkedList<…
14 июл '13 в 02:16
1
ответ
Числа Хэмминга для скорости O(N) и памяти O(1)
Отказ от ответственности: есть много вопросов по этому поводу, но я не нашел ни одного с требованием постоянной памяти. Числа Хэмминга это числа 2^i*3^j*5^kгде i, j, k - натуральные числа. Есть ли возможность генерировать N-е число Хэмминга с O(N) в…
12 май '16 в 23:27
1
ответ
Время и пространство сложность для удаления дубликатов из списка
У меня есть следующий код, и я пытаюсь получить сложность времени. seen = set() a=[4,4,4,3,3,2,1,1,1,5,5] result = [] for item in a: if item not in seen: seen.add(item) result.append(item) print (result) Насколько я понимаю, когда я получаю доступ к…
10 мар '17 в 04:07
2
ответа
Сложность, как времени, так и пространства
Я новичок в форуме, поэтому я надеюсь, что я делаю это правильно. Я борюсь с выяснением сложности BigO. В частности, сложность времени. Я сейчас работаю над рекурсивной программой, которая вызывает себя дважды каждый рекурсор. Пример: вычислить (I, …
09 мар '17 в 05:02
0
ответов
Javascript - Пространственно-временная сложность склейки и конкатов внутри цикла
У меня есть проблема, которая требует преобразования строки в другую путем добавления к ней копий ее начального значения. Проблема позволяет удалить отдельные символы в некоторых местах. объяснение let x = "abba"; // First string let y = "aba" // Se…
03 дек '18 в 19:35
1
ответ
Пространственная сложность сортировки слиянием в неизменяемом массиве
Пространственная сложность сортировки слиянием O(n) и метод выглядит void sort(int[] arr), Если я создаю метод int[] sort(int[] arr), который не изменяет входной массив, но возвращает новый отсортированный, то какова будет сложность пространства это…
10 янв '19 в 16:07
0
ответов
Какое влияние оказывает "Печать" на программу?
class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ a=[] count=0 while 1: print n c=n%10 n/=10 print c count+=c**2 print count if n==0: print "nEXT LOOP" print count print a if count in a: return False else: a.append(coun…
10 фев '19 в 21:51
2
ответа
Обновление списка занимает дополнительное место?
У меня есть array or listТеперь я хочу внести некоторые изменения в массив и вернуть обратно в arr variable/list, Я использую дополнительное пространство? или это та же самая переменная снова обновляется? arr = [1,2,3,4] print arr[2:] + arr[:2] # Is…
24 янв '17 в 20:38
1
ответ
Рассчитать время / пространство сложности при запуске программы
Я пробую различные типы алгоритмов сортировки и понимаю концепцию асимптотической сложности времени и пространства. Мне интересно, можем ли мы написать какую-то логику в самой программе, чтобы вычислить пространственно-временную сложность этого алго…
26 июн '15 в 05:59
0
ответов
Пространственная сложность для вспомогательного стека
На следующей диаграмме (когда вы открываете указанную ссылку), это подход для получения максимального элемента стека с использованием двух стеков (основного и вспомогательного стека). Сложность пространства равна O(n), так как я поддерживаю вспомога…
24 дек '18 в 09:09
1
ответ
Почему пространственная сложность рекурсивного метода, который создает двоичное дерево вызовов O(h)?
Учитывая этот метод: int f(int n) { if (n <= 0) { return 1; } return f(n - 1) + f(n - 1); } Создает стек стека / двоичное дерево следующим образом: n / \ n-1 n-1 / \ / \ n-2 n-2 n-2 n-2 etc например. n = 3 3 / \ 2 2 / \ / \ 1 1 1 1 / \ / \ / \ / …
21 окт '18 в 00:26
1
ответ
Разделяй и властвуй алгоритм для генерации n-битных строк?
Может кто-нибудь сказать, пожалуйста, как генерировать n-битные строки (все возможные комбинации), т.е. подсчитывать биты от 0 до 2^n-1, используя подход "разделяй и властвуй". Я смог сделать это с помощью следующего алгоритма, но сложность простран…
16 сен '12 в 18:24
3
ответа
Что такое временная и пространственная сложность словаря?
Давайте предположим, что у меня есть данные размером N (т.е.N элементов), и словарь был создан с емкостью N. Какова сложность: пробел - всего словаря время - добавление записи в словарь MS обнаружил только, что поиск записи близок к O(1). Но как нас…
25 окт '13 в 08:32
2
ответа
Необычные временные и пространственные сложности
Рассмотрим список A, состоящий из натуральных чисел. Есть ли следующий алгоритм for i in range(sum(A)-min(A)): print 'Hello world!' иметь O(sum(A)-min(A)) сложность времени? Таблица общих временных сложностей ничего не говорит о таких функциях, как …
14 июн '17 в 17:20
1
ответ
Как мне изменить структуру моего графика (очень медленная вставка)?
Эта программа, которую я делаю, посвящена социальной сети, то есть пользователям и их профилям. Структура профилей UserProfile, Теперь есть различные возможные реализации Graph, и я не думаю, что я использую лучшую. у меня есть Graph структура и вну…
08 апр '10 в 00:27
1
ответ
Космическая сложность против вспомогательной космической сложности
Я как будто путаюсь между этими двумя терминами, например: вспомогательное пространство сортировки слиянием, сортировки по типу heaps и сортировки вставкой равно O(1), тогда как сложность по пространству сортировки слиянием, сортировки вставки и сор…
26 июн '18 в 01:45
0
ответов
Временная сложность алгоритма для нахождения всех возможных слов телефонных цифр
Я изучаю эту проблему. http://www.geeksforgeeks.org/find-possible-words-phone-digits/ По моему мнению, временная сложность должна быть O(n^2), но там упоминается, что временная сложность для их алгоритма составляет O(4^n). Почему это 4^n? Какова буд…
01 ноя '14 в 21:37
2
ответа
ArrayList, содержащий ссылки на TreeNodes, какова сложность пространства?
TreeNode root = new TreeNode(5); ArrayList<TreeNode> arr = new ArrayList<TreeNode>(); for(int i = 0; i < n; i++){ arr.add(root); } В приведенном выше коде, один TreeNode объект добавлен в ArrayList<TreeNode> arr для п раз. я ду…
22 мар '15 в 07:25