algorithm - 计算大 O 复杂度

Question

在最近的一次考试中，我们得到了一个函数来计算在未排序的 ArrayList 中出现了多少个 double (不是原始 double，而是一个项目出现两次的次数)。

我正确地确定了 Big O 复杂度为 O(N^2)，但只得到了部分分数，因为我错误地确定了完整的复杂度。函数如下:

public static <T> int countDoubles(ArrayList<T> list, int index, Comparator<? super T> cmp) {
    if (index >= list.size())
        return 0;
    int count = 0;
    for (int i = index + 1; i < list.size(); i++) {
        if (cmp.compare(list.get(index), list.get(i)) == 0)
            count++;
    }
    return count + countDoubles(list, index + 1, cmp);
}

在他刚刚发布的考试答案中，他给出了这样的解释:

There are N items in the input collection, and the method calls itself over and over with a reduction step that produces a new index N times till it reaches the base case (end of the collection). For each recursive frame there is a for loop that work on one less element in the collection in each frame repeatedly until it reaches the end of the collection. So there are N recursive calls and N -1 steps for the first call, N-2 for the second, N-3 for the third and so on, until the end of the array is reached. This behavior has a quadratic growth in terms of the upper bound complexity as it will present the following expression:

T(N) = (N-1) + (N-2) + (N-3) + ... + 1 = N(N-1)/2 = ((N^2)/2) - (N/2) = O(N^2)

为了正确理解这一点，我尝试绘制一个大小为 10 的简单数组，每次将其检查的大小减一。

[] [] [] [] [] [] [] [] [] []
   [] [] [] [] [] [] [] [] []
      [] [] [] [] [] [] [] []
         [] [] [] [] [] [] []
            [] [] [] [] [] []
               [] [] [] [] []
                  [] [] [] []
                     [] [] []
                        [] []
                           []

计算递归级别是有意义的 N。计算出每个元素的结果是 9 + 8 ... = 45 考虑到 100(N 级递归 * N 元素)是 100，我不明白 N/2 从哪里来，更不用说 ((N^2)/2) - (N/2)。

非常感谢任何解释，因为过去一个月我一直在寻找并且似乎无法完全掌握我所缺少的东西。谢谢。

Answer 1

从1到M的整数之和是((M+1) * M)/2。这只是一个数学事实(通常通过归纳法证明)。如果您不相信，请尝试一些示例。

算法的第一遍做N-1compare，递归的每一层都少做一个compare，直到最后一个递归级别执行 1 compare。所以比较的总数(对于递归的所有级别)是从 1 到 N-1 的整数之和。将公式中的 M 替换为 N-1 得到的比较总数为 (N * (N-1))/2。

从那里开始，它只是代数

(N * (N-1)) / 2 = (N * N - N) / 2 = ((N^2) / 2) - (N / 2)

以这种方式分解它的原因是因为 big-O 只关心具有最大指数的 N。当然，big-O 也不关心常量。所以你扔掉 (N/2) 而忽略 /2 答案是 O(N^2)，这是最大的瓦 jar ...

好吧，别介意我对这件事的看法，事情就是这样。