算法的时间复杂度分析 - 求职面试

Question

最近，我遇到了一道面试题，需要编写一个算法来分析一个数组并返回其中重复的数字；

我的暴力解决方案是：

    public static ArrayList getDuplicates  (int[] input){
        ArrayList duplicates =  new ArrayList();
        int marker = 0;
        for (int i = marker + 1; (i < input.length) && (marker < input.length - 1); i++){
            if (input[marker] == input[i]){
                duplicates.add(input[marker]);
                marker++;
                continue;
            } else {
                if (i == input.length - 1){
                    marker++;
                    i = marker;
                }
                continue;
            }
        }
        return duplicates;
    } 

在没有经过彻底分析的情况下，我给出了一个答案：Big O是n*(log (n))。

面试后，我再次核对发现这不是正确的答案。

令人困惑的是算法重复执行，但不是n次，而是每个周期执行n-k次，其中k = {1..n-1}。这是重置移动索引的部分：

                if (i == input.length - 1){
                marker++;
                i = marker;
            }

什么是分析该算法以找到正确的大O函数的最佳方法？

- zakb

---

最坏情况下，时间复杂度似乎是n^2，因为如果找不到匹配项，则需要将每个元素与其他每个元素进行比较。如果没有找到匹配项，则必须执行input.length choose 2次比较。这种比较数量以二次方速率增加。 - Luke Kot-Zaniewski

一个用于存储重复元素的字典/哈希表可以让这个问题变得更加容易，也会将复杂度降低到 O(n)，但代价是需要更多内存。 - Michael Dorgan

大O符号是关于概括性的——你可以看到这是> O(n)，所以所有额外的工作都不值得——最好制定一个O(n)的解决方案。 - Hogan

你为什么要使用 ArrayList？它已经过时了，大约有十年了。如果我是面试官，一旦看到这个，我就会停止关注你的代码，因为我知道你没有资格。 - Servy

@ greybeard 是的，它总是终止的，因为它必须满足两个条件：（i <input.length）&&（marker <input.length-1），而i在每个循环后始终增加：因此在某一时刻，至少有一个条件将失败。 - zakb

Answer 1

我会分析的方法是插入边缘情况，然后看是否有任何模式出现：

1. 如果您有一个所有匹配项的数组会发生什么？ 在这种情况下，它是O（N），因为每次都会命中重复项的第一个条目。

2. 没有重复怎么办？ 那么，您需要通过整个数组扫描N^2 / 2次，因此是O（N^2）。

从中我们可以看到最好的情况是O（N），最坏的情况是O（N^2），我还想说平均情况也将是O（N^2）。

如果您使用嵌套for循环（一个用于原始数据扫描，另一个用于重复扫描），则N ^ 2行为将更容易发现。

如果相反，您将每个条目��加到具有O（1）添加能力（哈希表）的容器中，则算法变得更简单：

1. 对于输入数组中的每个项目，请尝试将值添加到哈希表中。 2. 如果值已经存在于哈希表中，请插入重复数组。 3. 完成foreach扫描并返回重复数组。

- Michael Dorgan