Пространственная сложность массива пар

Question

Так что мне интересно, какова пространственная сложность массива целочисленных пар?

std::pair<int,int> arr[n];

Я думаю, что, поскольку пара постоянна, а массив равен n, сложность пространства равна O(2) * O(n) = O(2n) = O(n). Или сложность пространства O(n^2), поскольку массив пар по-прежнему является двумерным массивом?

Answer 1

Правильная сложность пространства равна O (n)

Тот факт, что он внешне напоминает двумерный массив, несущественен: величина второго измерения известна, и как таковая она остается O (n).Это также было бы верно, если бы пары представляли собой массивы из 100 элементов.Поскольку размеры элементов (каждый массив из 100 элементов) известны, пространственная сложность структуры равна O (100 * n), что равно O (n).

И наоборот, если элементы быливместо этого явно всегда совпадает с размером контейнера в целом, то есть это было что-то вроде этого:

int n = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(n);
}

Тогда это действительно было бы O (n ² ) вместо этого.Поскольку теперь оба измерения зависят от неизвестной величины.

И наоборот, если второе измерение было неизвестно, но известно, что оно не связано с первым измерением, вы бы вместо этого выразили его как O (нм), то естьмассив построен следующим образом:

int n = /*...*/;
int m = /*...*/;
std::vector<std::vector<int>> arr(n);
for(std::vector<int> & subarr : arr) {
    subarr.resize(m);
}

Теперь это может показаться противоречивым: "Но Xirema, вы только что сказали, что если бы мы знали размеры были n X 100 элементов, это было быбыть O (n), но если мы заменим 100 на m, разве у нас не будет сложности пространства O (нм) или O (100n)? "

Но, как я уже сказал: мы удаляем известныевеличины.O (2n) эквивалентно O (5n), потому что все, что нас волнует, это неизвестные.Как только неизвестное становится известным, мы больше не включаем его в оценку сложности космоса.

Пространственная сложность (и сложность времени выполнения и т. Д.) Предназначены для функционирования в качестве абстрактных представлений алгоритма или структуры данных.Мы используем эти концепции, чтобы выработать на высоком уровне концепцию, насколько хорошо они масштабируются для больших и больших входов.Две разные структуры данных, одна из которых требует 100 байтов на элемент, другая требует 4 байта на квадрат в квадрате, не будет иметь согласованных пространственных рангов между собой при масштабировании от небольшой среды к большой среде;в меньшей среде последняя структура данных будет занимать меньше памяти, а в большей среде первая структура данных будет занимать меньше памяти.Сложность порядка пространства / времени выполнения - это всего лишь сокращение для выражения этих отношений без необходимости увязать в деталях или семантике.Если вам важны детали или семантика, то вы не просто будете использовать Порядок структуры / алгоритма, а будете на самом деле тестировать и измерять эти разные подходы.

Answer 2

Занимаемое место составляет n * sizeof(std::pair<int, int>) байт.sizeof(std::pair<int, int>) является константой, а O(n * (constant)) == O(n).

Answer 3

Пространственная сложность массива в общем случае может быть:

O(<size of array> * <size of each array element>)

Здесь у вас есть:

std::pair<int,int> arr[n];

Итак, arr - это массив с n элементами, а каждый элемент - это std::pair<int,int>. Предположим, что int занимает 4 байта, поэтому пара из двух int должна занимать 8 байтов (это число может немного отличаться в зависимости от реализации, но это не имеет значения для целей расчета сложности). Таким образом, сложность будет O(n * 8), что совпадает с O(n), потому что константы не имеют значения в сложности.

Когда у вас будет что-то вроде O(n^2)? Ну, вам понадобится многомерный массив. Например, что-то вроде этого:

std::pair<int,int> arr[n][m];

Теперь arr - это массив с m элементами, но каждый элемент в свою очередь является массивом n std::pair<int,int> элементов. Итак, у вас есть O(m * <size of array of n pairs>), то есть O(m * n * 8), то есть O(m * n). Если m совпадает с n, тогда вы получите O(n * n) или O(n^2).

Как вы можете себе представить, аналогичные рассуждения следуют для любого числа измерений массива.

Answer 4

РЕДАКТИРОВАТЬ:

извините, путали со сложностью времени.из-за того, что вы знаете размер и количество второго элемента в структуре (т. е. это не n, а постоянная), сложность пространства остается неизменной при O (n)