总结阵列和大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形表示法的算法的运行时间涉及它

这是过去一年考试，我需要做出修改为我的考试。

问题，点击 数组A []保持N个整数值被给予结果 确定公司运作的用于阵列中计算所有值的总和的算法结果 2.Find最简单的和最好的O形表示法用于该算法的运行时间。

Answer 1

的问题是找到所有的值的总和通过阵列中的每个元件，以便迭代和每个元素添加到临时总和值。

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

由于您需要经过所述阵列中的所有元素，这<强>程序线性地依赖于元素的数量。如果你有10个元素，遍历10个元素，如果你有一百万，你必须比其他没有选择去通过所有万台，并添加他们每个人。因此在时间复杂度为Θ（n）的

如果您发现所有元素的总和，你不知道，然后这些数据，您需要在所有的元素看起来至少一次的任何事情。因此n是下界。你也不用看元素不止一次。 n是也上限。因此，复杂度为Θ（n）中。

不过，如果你知道一些关于你得到n个自然数的列率的elements..say，你可以用N（N + 1）/ 2做它在固定的时间。如果你得到的数据是随机的，那么你别无选择，只能做了以上的线性时间算法。

Answer 2

由于<强>名词是阵列的尺寸和所有你必须做的是从开始迭代结束的大O符号是O [n]的

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

我觉得你的意思“而Ĵ<= N”，你需要指定此。

在运行时间应为O（n），我想，因为只有一个环。

Answer 4

要为这种算法需要计数的次数的代码的每一行执行的数量计算O操作。后来你只会算的基本操作，但通过计算所有启动。

所以多少次将第j：= 1行运行？多少次将总和：= 0运行？ while循环的条件会多少次执行？在while循环内的语句？

总结这些都放弃了。你会发现，你得到的价值会像1 + 1 + N + N + N = 2 + 3N。由此可以得出结论，它是n个线性函数。