java - 简单的固定大小整数算术的算法效率（以 Big-Oh 计）是多少？

Question

例如，

public int sumArray()
{
  int[] arr = new int[10];

  int n = arr.length;

  int sum = (n*(n+1))/2;

  return sum;
}

该算法的效率会是 O(1)、O(n) 还是其他？

Answer 1

通常假设基本整数的大小是一个常数，并且任何能够处理某些数量的项目的机器都将固有地具有足以容纳该数字的本机整数大小。如果不是这样的假设，大多数算法最终会得到额外的 O(lg(N)) 或 O(lg(N)^2) 因子，以适应所需整数大小为 O(lg(N) )，并且对大小为 S 的整数执行操作的总步骤数将是 O(S) 或 O(S*S) [实际上，大多数步骤将在现代硬件上并行执行，但总数步数仍然是 O(S) 或 O(S*S)]。

请注意，这些假设假设代码不需要使用长度超过 O(lg(N)) 的数字，但后一种假设通常在实践中成立；主要有必要防止算法使用任意长度的整数来执行在所谓的 O(1) 时间内不是 O(1) 的任务。

Answer 2

简单来说，据我了解（如果您想要更准确的官方信息，请访问谷歌或查看 wiki），

Big-O 让您了解特定算法的效率如何，例如，如果您想对列表进行排序/搜索已排序/未排序列表中的元素，基本上这需要针对项目大小进行迭代。随着尺寸开始变大，您将看到使用更有效算法的巨大改进。

在您的情况下，不涉及迭代，因此这将是常数时间 O(1)，n 的值是多少并不重要。但是，如果您使用从一到 n 的循环重写您的 Sigma N 问题并在每次迭代中求和，那么它将是 O(n)。如您所见，对于这个特定问题，您的解决方案比循环更有效。O(1) 优于 O(n)。

Answer 3

算法效率为 O(1)。没有争论，它是恒定的。如果您下次感到困惑，您应该查看Big-O 算法复杂性备忘单。

Answer 4

中的每个单独的语句都sumArray需要恒定的时间（与 的值无关，n这里它本身就是一个常数），所以整个函数也是如此。