algorithm - Big(O) 符号 - 哪个是正确的

Question

我正在尝试学习 Big(O) 表示法。在网上搜索一些文章时，我遇到了两篇不同的文章，A和 B

严格来说从循环的角度来说——似乎它们几乎具有相同的流程。 例如

[A]的代码如下(用JS实现)

function allPairs(arr) {
    var pairs = [];
    for (var i = 0; i < arr.length; i++) {
        for (var j = i + 1; j < arr.length; j++) {
            pairs.push([arr[i], arr[j]]);
        }
    }

    return pairs;
}

[B]的代码如下(用C语言完成)-整个代码是here

  for(int i = 0; i < n-1 ; i++) {
    char min = A[i]; // minimal element seen so far
    int min_pos = i; // memorize its position
    // search for min starting from position i+1
    for(int j = i + 1; j < n; j++) 
      if(A[j] < min) {
        min = A[j];
        min_pos = j;
      }
    // swap elements at positions i and min_pos
    A[min_pos] = A[i];
    A[i] = min;
  } 

A站的文章说时间复杂度是O(n^2)，B站的文章说是O(1/2·n2)。

哪个是对的？

谢谢

Answer 1

假设O(1/2·n2)表示O(1/2·n^2)，则两者时间复杂度相等。请记住，Big(O) 表示法不关心常量，因此两种算法都是 O(n^2)。