Вопросы по теме 'space-complexity'
Сложность времени и сложность пространства
Мой алгоритм показан ниже. Он делает удаленный вызов на сервер и получает результаты, обрабатывает их и снова отправляет удаленный вызов в систему. Можете ли вы дать мне представление о том, какова может быть временная и пространственная сложность...
1018 просмотров
schedule
30.05.2023
Алгоритм «разделяй и властвуй» для генерации n-битных строк?
Может кто-нибудь рассказать, как генерировать n-битные строки (все возможные комбинации), т.е. считать биты от 0 до 2 ^ n-1 с использованием подхода «разделяй и властвуй».
Я смог сделать это с помощью следующего алгоритма, но пространственная...
1430 просмотров
schedule
22.08.2022
Триплет, сумма которого находится в диапазоне (1,2)
Имея n положительных вещественных чисел в массиве, найдите существует среди этого набора триплет, сумма которого находится в диапазоне (1,
2) . Сделайте это в линейном времени и постоянном пространстве.
массив не упорядочен....
17542 просмотров
schedule
16.03.2022
Обратные символы каждого слова в предложении
Обратные символы каждого слова в предложении. Например:
Меня зовут Алекс
изменения в
yM eman si xela
Я подумал об обычном алгоритме времени O(n) , использующем два указателя, чтобы указать на любой конец слова и перевернуть...
385 просмотров
schedule
16.04.2023
Сложность пространства сортировки кучи
Я просто читал книгу Skiena Algorithm Design Manual, в частности раздел о сортировке кучей. Он заявляет, что
Это сортировка на месте, то есть она не использует дополнительную память для массива, содержащего сортируемые элементы.
алгоритм...
1169 просмотров
schedule
19.08.2022
Учитывает ли возвращаемое значение сложность пространства
Ниже приведен алгоритм, который используется для создания нескольких наборов. Именно это решает следующий вопрос Print all combination of element in the array such that first element of array is d and
next element in the array can be +1 or -1 the...
468 просмотров
schedule
18.04.2023
Каковы пространственные сложности inits и tails?
TL; DR
После прочтения отрывка о постоянстве в книге Окасаки Purely Functional Data Structures и изучения его иллюстративных примеров односвязных списков (именно так реализованы списки Haskell) я задумался. о космических сложностях inits и...
376 просмотров
schedule
16.09.2022
Разница в пространственной сложности различных алгоритмов сортировки
Я пытаюсь понять космические сложности различных алгоритмов сортировки.
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229 по приведенной выше ссылке Я обнаружил, что сложность пузырьковой сортировки, сортировки вставкой и выбором...
6573 просмотров
schedule
12.02.2023
Сложность времени и пространства для удаления дубликатов из списка
У меня есть следующий код, и я пытаюсь получить временную сложность.
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)
Насколько я...
1510 просмотров
schedule
30.06.2023
Как узнать, занимает ли алгоритм псевдополиномиальное время??
Получив вопрос, я пытаюсь его решить и предполагаю, что нашел алгоритм. Теперь я делаю анализ временной сложности для этого алгоритма и обнаруживаю, что он работает за полиномиальное время. Теперь как я могу убедиться, что мой алгоритм работает...
210 просмотров
schedule
31.05.2023
Сколько заказов BFS есть?
Учитывая граф G(V,E) и исходную вершину s , сколько имеется порядков BFS и как должен выглядеть алгоритм, чтобы найти их все?
Примеры
Граф только с одной вершиной A имеет ровно один порядок BFS для s=A , а именно [ A ].
Граф с двумя...
633 просмотров
schedule
18.09.2022
Самый длинный общий префикс — анализ сложности подхода «разделяй и властвуй»
Я пытаюсь понять, как была получена сложность времени и пространства для подхода D & C к поиску самого длинного общего префикса из массива строк. Пример: массив строк ["leet", "leetcode", "leeds","le"] и вывод будет "le" Это проблема с leetcode 14...
896 просмотров
schedule
05.02.2024
Будет ли этот алгоритм иметь пространственную сложность O(1) или O(n)?
У меня есть домашнее задание, которое просит меня найти пропущенное число в массиве с временной сложностью O (n) и пространственной сложностью O (1).
Я чувствую, что довольно хорошо понимаю, что представляет собой пространственная сложность O (1),...
75 просмотров
schedule
05.03.2024
Какой из следующих методов более эффективен
Постановка задачи: - Для массива целых чисел и целого числа k выведите все пары в массиве, сумма которых равна k.
Метод 1: - Отсортируйте массив и установите два указателя: низкий и высокий, начните повторение ...
Сложность времени - O...
93 просмотров
schedule
13.06.2022
Перекошенное двоичное дерево против идеального двоичного дерева - сложность пространства
Перекошенное двоичное дерево занимает больше места, чем, скажем, идеальное двоичное дерево?
Я решал вопрос № 654 - Максимальное двоичное дерево на Leetcode, где, учитывая массив, вы должны создать двоичное дерево так, чтобы корень был максимальным...
181 просмотров
schedule
30.05.2023
Какова пространственная сложность сортировки битов?
Какова пространственная сложность сортировки битов? Согласно наилучшему и среднему случаю это O (n). Мне интересно, какова его космическая сложность
Название источника: Битовая сортировка: новая техника сортировки
Исследование IEEE...
55 просмотров
schedule
03.08.2022
Объяснение и сложность видимых точек в кодовом бою
Я столкнулся с этим вопросом о кодовом бою / кодовом сигнале. Учитывая массив точек на плоскости, найдите максимальное количество точек, видимых из начала координат с углом обзора 45 градусов.
int...
345 просмотров
schedule
01.10.2022
Почему временная сложность нижеследующего фрагмента O (n), а пространственная сложность O (1)
Приведенный ниже код имеет пространственную сложность O (1). Я знаю, что это как-то связано со стеком вызовов, но я не могу его правильно визуализировать. Если бы кто-нибудь мог заставить меня понять это немного яснее, было бы здорово.
int...
68 просмотров
schedule
14.02.2024
Каков эффективный способ добиться максимального параллелизма в списке кортежей?
Я пытался эффективно решить эту проблему. Проблема в:
Заявление о проблеме
Дан список кортежей в форме [(start1, end1), (start2, end2), (start3, end3)....(startn, endn)] , где начало и конец - положительные целые числа. Каждый кортеж должен...
164 просмотров
schedule
25.02.2022
Какова временная и пространственная сложность этого кода повторяющегося шаблона подстроки? (Код написан на Java)
Я написал это решение для проблемы LeetCode # 459. https://leetcode.com/problems/repeated-substring-pattern/ I хотите знать время выполнения и пространственную сложность этого решения. Я предполагаю сложность выполнения O (logN N), где N - длина...
34 просмотров
schedule
03.04.2022