求和数组和大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符号.

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的恒定时间内完成.如果您获得的数据是随机的,那么您别无选择,只能执行上述线性时间算法.