计算大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);
}

在他刚刚发布的考试解决方案中，他给出了这样的解释：

输入集合中有N个项，该方法通过一个缩减步骤反复调用自己，该步骤生成一个新索引N次，直到达到基本情况（集合结束）。对于每个递归帧，都有一个For循环，该循环在每个帧中重复处理集合中少一个元素，直到它到达集合的末尾。因此，有N个递归调用，第一个调用有N-1个步骤，第二个调用有N-2个步骤，第三个调用有N-3个步骤，依此类推，直到到达数组末尾。此行为在上界复杂性方面具有二次增长，因为它将呈现以下表达式：

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-1比较，每一级递归执行一次比较，直到最后一级递归执行1比较。因此，比较的总数（对于所有递归级别）是从1到N-1的整数之和。用公式中的N-1代替M，得出的比较总数为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），这是最大的crck o'...

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