对整数数组求和的最有效方法

Question

我正在尝试寻找一个子< code>O(n)方法来计算一个整数数组的和~~~(不是遍历< code>0 - n，我是在< code>n/2中做的)~~~我还是在O(n)中做的。

public static int sum(int[] s) {
    int length = s.length - 1;
    int half = length/2;
    int sum = 0;
    for(int i = 0; i <= half; i++) {
        System.out.println(i + " " + s[i] + " + " + s[length - i]);
        sum += s[i] + s[length - i];
    }
    return sum;
}

我的算法适用于偶数个整数，但是，当整数数为奇数时，它会将中间索引求和两次：

测试：

    int[] arr = {1, 2, 3, 4, 5};
    System.out.println(sum(arr));

输出：

0 1 + 5
1 2 + 4
2 3 + 3
Sum: 18

我的问题是——对奇数的中间索引求和的最佳方法是什么？

Answer 1

你的解是O(n)，不是子O(n)。仅仅在循环中增加两个数并不能改变它。没有办法使它小于O(n ),因为你需要迭代所有的数字。

Answer 2

这仍然是O（n），即使你在一天结束时从0到n/2，你至少触摸了数组的每个元素一次。为了对一个整数数组求和，你至少可以做的是O（n），因为你必须触摸数组中的每个元素一次才能将其包含在总和中。