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

Question

我正在尝试寻找一种O(n)的子方法来计算一个整数数组的总和~~~（而不是遍历0-n，我在使用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

我的问题是 - 怎样最好地计算奇数个数字的中间索引的总和？

- theGreenCabbage

---

请注意，这仍然是O(n)。你进行了相同数量的加法运算。你只是避免了i的n次自增操作，但现在你需要进行减法运算。 - IVlad

O(n) 等于 O(n/2)。 - PM 77-1

如果您的数组值遵循趋势，例如索引，那么它可能小于O(n)，否则最低为O(n)。 - user3437460

现实生活中的效率与大O并不那么密切相关，常数因素很重要。那么你想要什么，理论时间复杂度（显然不能比O（n）更好）还是实际效率？ - harold

非常感谢大家 - 实际上，这种方式如果实现正确，比逐个索引迭代要慢。我现在感觉很愚蠢 =) - theGreenCabbage

如果数组只包含一个元素，您将会遇到问题。 - Mohamed AbdElRazek

Answer 1

即使你在一天结束时从0到n/2，仍然是O(n)，因为你至少要触摸数组的每个元素一次。而对于整数数组的求和，最少需要O(n)的时间，因为你必须至少触摸一次数组中的每个元素才能将其包含在总和中。

- Amr

---

糟糕，我不知道这个..哎呀。所以用这种方式和遍历每个元素并求和相比没有任何好处吗？ - theGreenCabbage

完全不是这样，你其实让它变得更复杂了 :) - Amr

哈哈..我正在将字符串反转技术（其中您交换i和length-i索引）应用于此问题。我想我真的想太多了。 - theGreenCabbage

@theGreenCabbage 不是的。实际上，正确实现你的方法会比简单地迭代所有索引并求和元素要慢。 - Fernando Matsumoto

@FernandoMatsumoto 我同意，因为我需要一个条件语句来确定它是奇数还是偶数。 - theGreenCabbage

是的，但即使字符串交换技术也是O(n)。当您尝试获取算法的顺序时，请始终考虑您访问数组中的每个元素的次数。此外，@FernandoMatsumoto是正确的，不仅因为奇偶性，还因为内存缓存，当您按顺序访问数组时，您利用了缓存，而以您所做的方式访问它更有可能导致页面错误。 - Amr

Answer 2

你的解决方案是O(n)，而不是sub-O(n)。仅仅在循环内部添加两个数字并不能改变它。因为你需要遍历所有数字，所以没有办法使它成为sub-O(n)。

- Michael D