algorithm - 对数组和大 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 将其与算法的运行时间联系起来

这是去年的考试，我需要复习。

问题
给出一个包含 n 个整数值的数组 A[]
1.给出一个计算数组中所有值之和的算法
2.为算法的运行时间找到最简单最好的O-notation。

Answer 1

问题是找到所有值的总和，因此遍历数组中的每个元素并将每个元素添加到一个临时总和值。

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

由于您需要遍历数组中的所有元素，因此此程序与元素数量呈线性关系。如果你有 10 个元素，迭代 10 个元素，如果你有 100 万个元素，你别无选择，只能遍历所有百万个元素并添加每个元素。因此时间复杂度为Θ(n)。

如果您要计算所有元素的总和，而您对数据一无所知，那么您需要至少查看所有元素一次。因此 n 是下界。您也不需要多次查看该元素。 n 也是上限。因此复杂度为 Θ(n)。

但是，如果您对元素有所了解……比如说您得到了 n 个自然数的序列，您可以在常数时间内用 n(n+1)/2 来完成。如果您获得的数据是随机的，那么您别无选择，只能执行上述线性时间算法。