java - 哪个更快？(来自CTCI书)

Question

我在 CTCI 书中看到了这两个代码片段，

代码片段 1:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE; 

for(int x : array) { 
    if (x < min) min = x;
    if (x > max) max = x;
}

代码片段 2:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE; 

for(int x : array) { 
    if (x < min) min = x;
}

for(int x : array) {
    if (x > max) max = x;
}

从汇编级别和编译器优化的角度来看，这本书没有给出一个更快、更高效的明确答案。我相信这两者都有 O(n) 运行时间。第一个有一个循环，代价是两个条件操作，而第二个，循环两次，只有一个条件操作。

从技术上讲，第二次运行时间为 O(2N)，第一次运行时间为 O(N)，但由于我们省略了常量，因此两者都将描述为 O(N)。那么假设 N 很大，常数真的很重要吗？另外，从编译器的角度来看，哪一个会产生更优化的汇编代码？

编辑:常量对于 N 的大尺寸无关紧要，但是比较两个代码片段，其中一个的常数为 2，另一个没有，如果我们同时运行这两个代码片段，它会影响运行时间吗它们在相同大小的 N 和相同的机器规范上并行？

Answer 1

To be technically precise the second run time would be O(2N) and the first one O(N) but since we omit the constants, both would be described as O(N).

我认为这是不对的。 就比较的数量而言(这就是这里的本质)，在第一种情况下，您每次迭代进行2 比较，而在第二种情况下有两个循环，但每个循环都有 1 比较。所以，这两个是等价的，因为 O(2N) = O(N) + O(N)。

当然，一些正确的注释揭示了运行此类代码的实际方面 in silico .我们发现算法的 Big-Oh 复杂性的真正原因是了解计算的行为如何不考虑计算(机器)能力并且存在任意大的 N，输入大小(这就是为什么我们说渐近)。