Какова космическая сложность моего кода?
Мне достаточно комфортно со сложностями времени, но еще не со сложностями пространства. У меня был следующий вопрос о сложности пространства:
unordered_set<int> s;
for(auto& i : nums)
s.insert(i);
Насколько я понимаю, сложность пространства приведенного выше фрагмента кода O(n) (n количество элементов во входном векторе nums) потому что я создаю набор вне цикла for и вставляю в максимуме n элементы в нем.
Однако, если бы я создал набор внутри цикла for, как:
for(auto& i : nums) {
unordered_set<int> s;
s.insert(i);
}
тогда в этом случае моя сложность пространства снова будет O(n)? Я понимаю, что я делаю по-разному (создавая новый набор каждый раз и вставляя в него только один элемент), но мне просто любопытно, насколько сложен космос.
Короче говоря, зависит ли сложность пространства только от того, сколько элементов вставлено в структуру данных, или также от того, сколько структур данных используется (например, создание их в цикле).
Благодарю.
Решение
Во втором случае сложность пространства O(1) и первый случай это O(n),
Второй случай ..
Если вы рассматриваете второй случай в цикле каждый раз, когда вы объявляете локальный unordered_set а затем вы нажимаете 1 элемент. И тогда это не используется, и снова другая итерация. В большинстве 1 или постоянное количество места используется.
Первый случай ..
В первом случае вы берете set а затем вставьте элементы. В большинстве n элементы, которые вы вставляете. Вот почему O(n),
Некоторое определение
Для каждого размера ввода алгоритм будет принимать определенное количество
пространства. Без лишних усложнений можно сказать, что, возможно, он используется
сохраните результат или какую-то работу, которую вам необходимо выполнить в промежуточном порядке. Как
многие структуры данных, которые вы используете, не проблема используемое пространство
ими является.
Пространственная сложность связана с выяснением того, сколько (дополнительного) пространства потребуется алгоритму с изменением размера ввода.
Теперь давайте проверим одну вещь, предположим, что вы увеличиваете количество входных данных в первом случае с n=100 в n=100000 тогда что будет лишней памяти, которая вам понадобится. Как вы увидите, это увеличивается линейно. (До 100 входные 100 элементы набора сейчас 100000).
Во втором случае это нужно? Вы всегда используете только 1 пространство. (Постоянное количество пространства). И тогда вы отказываетесь от этого. И в новой итерации вы работаете с другим пространством. Только сразу 1 элемент есть. Так что, какой бы ни был ввод, он всегда будет одинаковым.
Чтобы быть более понятным, если вы используете в каждой итерации, вы вставляете 3 элементы это не меняет сложность пространства .. это все равно будет O(1) временная сложность, означающая, что он использует постоянный объем пространства (независимо от размера ввода).
Другие решения
Сложность пространства показывает, сколько памяти использует ваш алгоритм.
Во втором случае вы вставляете только один элемент в s, Сразу после этого s выходит из области видимости, и вы начинаете новую итерацию. Это означает, что вы фактически используете только один блок памяти одновременно. Использование памяти не увеличится с n, Таким образом, у вас есть O(1),
Во втором случае ваша сложность O(1),
Каждая итерация будет использовать set только один раз, и тогда он будет освобожден.
В общем, сложность зависит от общего места, которое требуется вашей программе.
В вашем случае вы будете использовать n раз установить размер 1, но он не будет накапливаться.
Во втором случае каждый unordered_set перестает существовать после окончания тела цикла. Разумная реализация будет повторно использовать одно и то же пространство для всех наборов, и они будут содержать только один элемент.
Если вы используете это в качестве метрики сложности пространства, то первый случай имеет O(n) требуется дополнительное пространство, а во втором случае O(1) требуется дополнительное пространство
Сложность пространства — это мера того, как объем необходимого хранилища для вашего алгоритма увеличивается в зависимости от вашего размера ввода.
Предполагая, что вы вставляете n уникальные целые числа, std::unordered_map действительно придется выделить достаточно места для хранения n узлы, в дополнение к некоторым постоянным значениям, на которые не влияет число целых чисел, которые вы вставляете в него. Следовательно, сложность пространства действительно будет O (n).
Во втором примере, независимо от того, сколько чисел в num, вы всегда будете выделять достаточно памяти для одного целого числа в std::unordered_set, Следовательно, сложность вашего пространства равна O (1).
С точки зрения сложности, запас хранилища безграничен, и все, что имеет значение, это то, сколько его вы используете одновременно.
Рассмотрим проблему измерения X ведер воды.
Это не имеет никакого значения для сложности пространства, будь то вы
- Имейте одно ведро, которое вы наполняете, затем опорожняете, затем снова заполняете, затем опорожняете,
- Наполните одно ведро и выбросьте ведро, затем наполните другое ведро и выбросьте его, …
так как вы всегда используете не более одного ведра в любой момент времени.
Сами ведра не учитывают сложность, а только количество, которое вы держите одновременно.
С другой стороны, если бы у вас было не одно, а X ведер, которые вы наполняете (возможно, вы хотите сэкономить воду для предстоящей засухи), сложность пространства будет O (X).