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

StackOverflow https://stackoverflow.com/questions/904156

  •  05-09-2019
  •  | 
  •  

Вопрос

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

Есть ли Что-то подобное этому? 

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-нотацию

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

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

Это было полезно?

Решение

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

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.Если данные, которые вы получаете, случайны, то у вас нет выбора, кроме как выполнить описанный выше алгоритм линейного времени.

Другие советы

С тех пор как 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

Я думаю, что вы имели в виду "в то время как дж <= N", вам нужно указать это.

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top