algorithm - 复杂性和伪代码解释

Question

我们有以下伪代码

Input: An array A storing n ≥ 1 integers.
Output: The sum of the elements in A.
s←A[0]
for i←1 to n−1 do
s←s+A[i]
return s

首先，我一直在这样的伪代码中注意到这一点，为什么我们写 for i←1 to n−1 do 而不是例如 i←1 to n do 或 for i←1 to n+1 do ?

其次，这个的复杂度是 O(n-1) 所以 O(n)..我理解为什么它是 O(n)，这就是我看到代码时的想法，但为什么 O(n-1)首先 ？

编辑:我想了解的是我们是如何得到 O(n-1)

Answer 1

算法的复杂度为O(N)。对于计算机 O(N+1) ， O(N) ， O(N-1) ， O(N-2) 几乎相同(尤其是当 N 很大时)。所以每个人都将其近似为 O(N)。 他将 i 设置为 N-1 值，因为数组的起始索引为 0。所以你有:

A[0] , A[1] ...., A[N-1] ---> 数组中的 N 个元素。