Я запутался в сложности космоса

Question

Я немного запутался в сложности космоса.

int fn_sum(int a[], int n){
    int result =0;          
    for(int i=0; i<n ; i++){
        result += a[i];
    }

    return result;
}

В этом случае пространственная сложность O (n) или O (1)? Я думаю, что он использует только результат, я переменные, так что это O (1). Какой ответ?

Answer 1

(1) Space Complexity: сколько памяти ваш алгоритм выделяет в соответствии с размером ввода?

int fn_sum(int a[], int n){
    int result = 0;              //here you have 1 variable allocated       
    for(int i=0; i<n ; i++){
        result += a[i];
    }
    return result;
}

, поскольку переменная, которую вы создали (result), является одиночной значение (это не список, массив и т. д. c.), ваша сложность пространства равна O (1) , поскольку использование пространства равно константа , то есть: is isn не изменяется в зависимости от размера входных данных, это просто одно и постоянное значение.

---

(2) Time Complexity: как число операций вашего алгоритма связано с размер ввода?

int fn_sum(int a[], int n){      //the input is an array of size n
    int result = 0;              //1 variable definition operation = O(1)   
    for(int i=0; i<n ; i++){     //loop that will run n times whatever it has inside
        result += a[i];          //1 sum operation = O(1) that runs n times = n * O(1) = O(n)
    }
    return result;               //1 return operation = O(1)
}

все операции, которые вы выполняете, O (1) + O (n) + O (1) = O (n + 2) = O ( n) время, следуя правилам удаления мультипликативных и аддитивных констант из функции.

Answer 2

Я отвечаю немного по-другому: поскольку пространство памяти , потребляемое int fn_sum(int a[], int n), не коррелирует с количеством элементов ввода, его алгоритмы c сложность в этом отношении составляет O (1).

Однако сложность времени выполнения равна O(N), поскольку она повторяется по N элементам.

И да, есть алгоритмы, которые потребляют больше памяти и работают быстрее. Classi c один - это операции кеширования. https://en.wikipedia.org/wiki/Space_complexity

Answer 3

Другой способ вычислить сложность пространства - это проанализировать, увеличивается ли объем памяти, требуемый вашим кодом, в соответствии с заданным вводом.

Ваш ввод int a[] с размером n. Единственная объявленная вами переменная - result.

. Независимо от размера n, result объявляется только один раз. Это не зависит от размера вашего ввода n.

Следовательно, вы можете сделать вывод, что сложность пространства равна O(1).

Answer 4

Если int означает 32-разрядный целочисленный тип со знаком, сложность пространства равна O (1), поскольку вы всегда выделяете, используете и возвращаете одно и то же количество бит.

Если это это просто псевдокод и int означает целые числа, представленные в их двоичных представлениях без начальных нулей и, возможно, с дополнительным знаковым битом (представьте, что этот алгоритм выполняется вручную), анализ более сложный.

Если допускаются отрицательные значения, в лучшем случае - чередование положительных и отрицательных чисел, чтобы результат никогда не выходил за пределы постоянного размера - пробел O (1).

Если разрешен ноль, одинаково хорошим случаем является помещение нуля в весь массив. Это также O (1).

Если разрешены только положительные числа, лучший вариант сложнее. Я ожидаю, что в лучшем случае какое-то число будет повторяться n раз. В лучшем случае нам понадобится наименьшее представимое число для количества задействованных бит; Итак, я ожидаю, что число будет степенью 2. Мы можем вычислить сумму в терминах n и повторного числа:

result = n * val
result size = log(result) = log(n * val) = log(n) + log(val)
input size = n*log(val) + log(n)

По мере того, как val растет без ограничений, логарифм (val) доминирует в размере результата, а член n * log (val) доминирует во входном размере; таким образом, наилучший случай подобен мультипликативной обратной величине входного размера, а также O (1).

Наихудший случай следует иметь, выбрав val как можно меньшим (мы выбираем val = 1). и позволяя n расти без ограничений. В этом случае:

result = n
result size = log(n)
input size = 2 * log(n)

На этот раз размер результата увеличивается как половина размера ввода при увеличении n. Пространство в худшем случае является линейным.