c++ - 为什么在相同时间复杂度下，一种算法比另一种算法快？

Question

我当时正在应对编码挑战:双人赛。
目的是找到列表中两个元素之间的最小差异。

我从第一个算法开始，我认为它是O(nlog(n))，但是对于大型数组，执行超时。

int array[N];
int min = numeric_limits<int>::max();

for (int i = 0; i < N; i++) {
  int value;
  cin >> value;
  cin.ignore();
  array[i] = value;

  for (int j = i - 1; j >= 0; --j) {
    int diff = abs(array[j] - value);
    if (diff < min) {
      min = diff;
    }
  }
}

然后，我尝试了另一种也是O(nlog(n))的算法，这一次执行及时完成了。

int array[N];
int min = numeric_limits<int>::max();

for (int i = 0; i < N; i++) {
  int value;
  cin >> value;
  cin.ignore();
  array[i] = value;
}

sort(array, array + N);

for (int i = 1; i < N; ++i) {
  int diff = abs(array[i - 1] - array[i]);
  if (diff < min) {
    min = diff;
  }
}

我对第一个代码的复杂性有误吗？我没有注意到有什么区别吗？

谢谢你的帮助。

Answer 1

Am I wrong with the first code complexity?

是的，您错了，这种复杂度不是O(n log n)，而是O(n ^ 2)。

外循环平均运行n(N)次，而内循环平均运行n / 2次。因此，复杂度为O(n * n / 2)，即O(n ^ 2)，因为乘法常数在复杂度计算中无关紧要。

Is there any difference that I did not notice?

就在这里。即使您有两种算法具有相同的复杂度(例如O(n log n))，由于隐藏常数(在渐近复杂度行为中会被忽略)，它们都可以在非常不同的时间内运行。