如何找到计算数组中和值的算法？
是这样的吗？
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 表示法。
问题是找到所有值的总和，因此遍历数组中的每个元素并将每个元素添加到临时总和值。
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 在恒定时间内完成。如果您获得的数据是随机的，那么您别无选择，只能执行上述线性时间算法。
由于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
我认为您的意思是“当 j <= N”时，您需要指定这一点。
我认为运行时间应该是 O(n)，因为你只有一个循环。
要计算此算法的 O，您需要计算每行代码执行的次数。稍后您将只计算基本操作，但从计算所有操作开始。
那么 j := 1 行会运行多少次？sum := 0 会运行多少次？while 循环的条件将执行多少次？while 循环中的语句？
总结这些。你会注意到你得到的值类似于 1 + 1 + n + n + n = 2 + 3n。因此，您可以得出结论，它是 n 上的线性函数。