Пространственная сложность инициализированной структуры данных указателя
У меня есть вопрос.
С точки зрения теоретической информатики, когда мы анализируем алгоритм, если алгоритм инициализирует новую структуру данных, то мы рассматриваем эту структуру данных как часть сложности пространства.
Теперь я не слишком уверен в этой части тогда.
Допустим, у меня есть массив int и я хотел бы отобразить их с помощью карты int указатели. Такие как
std::map<int*,int*> mymap;
for (int i = 1; i < arraySize; i++) {
mymap[&arr[i-1]]=&arr[i];
}
Если бы этот алгоритм не использовал указатели, то мы могли бы четко заявить, что он инициализирует карту размером n, следовательно, сложность пространства равна O (n), однако для этого случая, когда мы используем указатели, какова будет сложность пространства этого алгоритма?
Решение
Пространственная сложность одного указателя такая же, как и у любого другого примитива, т.е. O(1),
std::map<K,V> реализован в виде дерева N узлы. Его космическая сложность O(N*space-complexity-of-one-node)Таким образом, общая сложность пространства в вашем случае O(N),
Обратите внимание, что система обозначений big-O выделяет постоянный множитель: хотя сложность пространства big-O std::map<Ptr1,Ptr2> а также std::vector<Ptr1> то же самое, множитель для карты выше, потому что построение дерева накладывает свои накладные расходы на хранение узлов дерева и связей между ними.
Другие решения
Других решений пока нет …