Суммирование массива и обозначение Big O

Question

Как найти алгоритм для вычисления значения суммы в массиве ??

Это что-то вроде этого?

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

И как я могу связать это со временем выполнения алгоритма, используя O-Notation

Это экзамен за прошлый год, и мне нужно пересмотреть экзамен.

Вопрос
Массив A [], содержащий n целых значений, задается
1. Дайте алгоритм для расчета суммы всех значений в массиве
2. Найдите простейшие и лучшие O-обозначения для времени выполнения алгоритма.

Answer 1

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

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

Так как вам нужно пройти через все элементы в массиве, эта программа линейно зависит от количества элементов . Если у вас есть 10 элементов, переберите 10 элементов, если у вас есть миллион, у вас нет другого выбора, кроме как просмотреть все миллионы элементов и добавить каждый из них. Таким образом, сложность времени равна Θ (n) .

Если вы находите сумму всех элементов и ничего не знаете о данных, то вам нужно взглянуть на все элементы хотя бы один раз. Таким образом, n является нижней границей. Вам также не нужно смотреть на элемент более одного раза. n также верхняя граница. Следовательно, сложность Θ (n).

Однако, если вы что-то знаете об элементах ... скажем, вы получаете последовательность из n натуральных чисел, вы можете сделать это за постоянное время с помощью n (n + 1) / 2. Если данные, которые вы получаете, являются случайными, то у вас нет выбора, кроме как выполнить описанный выше алгоритм линейного времени.

Answer 2

Так как n - это размер массива, и все, что вам нужно сделать, это перебрать от начала до конца, что обозначение Big O - O [n]

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

Чтобы вычислить O для этого алгоритма, вам нужно посчитать, сколько раз каждая строка кода выполняется. Позже вы будете считать только основные операции, но начнете с подсчета всех.

Так сколько раз будет выполняться строка j: = 1? Сколько раз будет работать сумма: = 0? Сколько раз будет выполняться условие цикла while? Операторы внутри цикла while?

Подведите итог. Вы заметите, что полученное значение будет примерно таким: 1 + 1 + n + n + n = 2 + 3n. Таким образом, вы можете сделать вывод, что это линейная функция от n.

Answer 4

Я думаю, что вы имели в виду "while j <= N", вам нужно это указать. </p>

Время выполнения должно быть O (n), я думаю, поскольку у вас есть только один цикл.