Вопросы по теме 'space-complexity'
Пространственная сложность обхода порядка обхода уровней с использованием очереди
Это код обхода порядка уровней:
public void bfsTraveral() {
if (root == null) {
throw new NullPointerException("The root cannot be null.");
}
int currentLevelNodes = 0;
int nextLevelNodes = 0;
final...
2736 просмотров
schedule
15.07.2023
Как определить память и временную сложность алгоритма?
Я не умею определять время и сложность памяти и был бы признателен, если бы кто-нибудь помог мне.
У меня есть алгоритм, здесь, и я не уверен, каковы будут его сложность времени и памяти.
Function sample(k)
IF k < 2
Return 0...
18124 просмотров
schedule
11.08.2022
Почему хеш-таблица занимает больше памяти, чем другие структуры данных?
Я читал о хеш-таблицах , словарях и т. д. Вся литература и видео, которые я смотрел, подразумевают, что хеш-таблицы обладают свойством компромисса между пространством и временем.
Я изо всех сил пытаюсь понять, почему хеш-таблица занимает больше...
5052 просмотров
schedule
07.05.2022
Пространственная сложность печати всех путей от корня до листа
Какова пространственная сложность хранения пути т.е. узлы двоичного дерева от корня до определенного листа в массиве?
В основном я ищу пространственную сложность следующего алгоритма:
public void printPath () {
doPrint(root, new...
487 просмотров
schedule
30.03.2022
Что лучше с точки зрения сложности - использовать функцию map () в Python или в понимании?
Как говорится в вопросе. map (f, iterable) может быть записан как [f (x) for x in iterable]. Что лучше использовать? И почему?
В качестве примера я хотел бы преобразовать список строк в int.
ip = (raw_input().split())
ip = [int(x) for x in...
6282 просмотров
schedule
14.07.2022
Какова пространственная сложность этого алгоритма?
Это задача 9.6 из Cracking the Coding Interview (5 ое издание)
Реализуйте алгоритм для вывода всех допустимых комбинаций n пар скобок ПРИМЕР Ввод: 3 Вывод: "((())), (()()) , (())(), ()(()), ()()()"
Вот алгоритм, который я реализовал (на...
731 просмотров
schedule
18.08.2022
рассчитать временную/пространственную сложность во время работы программы
Я пробую разные типы алгоритмов сортировки и понимаю концепцию асимптотической временной и пространственной сложности.
Мне интересно, можем ли мы написать некоторую логику в самой программе, чтобы вычислить пространственно-временную сложность этого...
445 просмотров
schedule
02.11.2022
Компактная структура данных для частичных продуктов последовательности?
Мне нужно предложить структуру данных со сложностью памяти O(n) , которая выполняет следующие действия:
Init() — инициализировать пустую структуру данных.
Insert (I,x) - вставить на I место число x. числа, которые были раньше на I месте и...
279 просмотров
schedule
03.01.2024
Как сортировка слиянием имеет пространственную сложность O (n) для наихудшего случая?
Сложность O(n) означает, что сортировка слиянием в худшем случае занимает пространство памяти, равное количеству элементов, присутствующих в исходном массиве. Но разве он не создал новые массивы при выполнении рекурсивных вызовов? Как это место не...
3433 просмотров
schedule
29.05.2022
Попытка понять пространственную сложность этого алгоритма
Я вижу много статей в Интернете, объясняющих временную сложность, но не нашел ничего хорошего, что хорошо объясняет пространственную сложность. Я пытался решить следующий вопрос интервью
У вас есть два числа, представленные связанным списком,...
219 просмотров
schedule
01.08.2022
Можно ли вычислить функцию подсчета простых чисел и произведение последовательных простых чисел за полиномиальное время?
В двух алгоритмах, с которыми я работал, я использую две функции:
pi(n):=количество простых чисел ‹= n и
R(n):=r , где prod(p_i,i=1,r)‹=n , но n ‹ prod(p_i,i=1, r+1) , где p_i — i-е простое число.
По сути, pi(n) — это известная...
244 просмотров
schedule
03.09.2022
Алгоритм Беллмана-Форда Пространственная сложность
Я искал пространственную сложность алгоритма Беллмана-Форда, но в википедии Алгоритм Беллмана-Форда и говорит, что пространственная сложность равна O(V). на этой ссылке написано O(V^2) . Мой вопрос; какова истинная космическая сложность и почему?
3213 просмотров
schedule
13.06.2022
Какова временная и пространственная сложность кодирования Хаффмана?
Я реализовал алгоритм кодирования Хаффмана, используя (две) хэш-карты для хранения частоты и кода каждого уникального символа (хранящегося как ключи в хэш-картах) (хранящегося как значение в хэш-картах). Я не уверен, как я могу определить сложность...
2495 просмотров
schedule
03.09.2022
Смущен пространственной сложностью следующего алгоритма
Я просматривал вопрос utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa">Link и сообщает, что пространственная сложность решения равна O(1) (см. ответ Макс ). Я сомневаюсь, что пространственная сложность - это пространство,...
44 просмотров
schedule
29.03.2023
Пространственная сложность добавления строк Java char за char
При построении строки Java char за символом через цикл через «сложение» можно заметить, что сложность времени выполнения этой операции невелика: она квадратична O(n^2) время. Тем не менее, мне интересно, является ли пространственная сложность...
809 просмотров
schedule
11.04.2023
Временные и пространственные сложности алгоритмов сжатия, таких как LZ4, Snappy, Zstandard и Deflate
Я ищу временные и пространственные сложности вышеуказанных алгоритмов, но я не могу найти их в Google, я потратил более двух дней без какого-либо результата. Я был бы очень благодарен, если бы вы, ребята, мне помогли.
227 просмотров
schedule
06.07.2023
Причина экспоненциального ускорения, ожидаемого от квантовых компьютеров
В квантовых компьютерах должны наблюдаться два эффекта:
1) Если оператор действует на произвольный QuBit Qn квантовой системы S, состоящей из нескольких QuBit, то мы получаем новую квантовую систему S', в которой изменились амплитуды ВСЕХ QuBits....
45 просмотров
schedule
15.09.2022
что занимает больше места: объект с 2 ключами или 2 значения переменных? Как лучше?
Или они практически одинаковые? Лучше ли использовать один или другой, если я знаю, что мне нужно только 2 части информации для функции?
const twoKeyValPairs = {a:1, b:2};
vs
const a = 1;
const b = 2;
61 просмотров
schedule
29.06.2022
Временная сложность и пространственная сложность следующего фрагмента кода
double foo(int n)
{
int i;
double sum;
if(n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for(i = 0; i < n; i++)
{
sum += foo(i);
}
return sum;
}
}
Я...
107 просмотров
schedule
23.04.2023
найти временную и пространственную сложность
Мне нужно найти временную и пространственную сложность f3 . Я думаю, что g имеет пространственную сложность log(n) , поэтому для временной сложности, но я не совсем уверен, как мне найти временную и пространственную сложность f3 , потому что...
81 просмотров
schedule
17.09.2022