Суммирование массива и обозначения Big O
Вопрос
Как найти алгоритм для вычисления суммарного значения в массиве??
Есть ли Что-то подобное этому?
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.