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

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

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). Каков ответ?

Всего 3 ответа


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

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

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


(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 ), представляет собой одно значение (это не список, массив и т. д.), ваша сложность пространства равна O (1) , поскольку использование пространства является постоянным , то есть: не изменяется в соответствии с к размеру входов, это просто одно и постоянное значение.


(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) , следуя правилам удаления мультипликативных и аддитивных констант из функции.


Если 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 растет без ограничений, термин log (val) доминирует в размере результата, а термин n * log (val) доминирует во входном размере; Таким образом, наилучший случай подобен мультипликативной обратной величине входного размера, а также O (1).

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

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

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


Есть идеи?

10000