重复检测算法的复杂性

Question

我不太熟悉复杂度表示法，谁能帮我确定这个算法的复杂度？

for (int i = 0; i < records.size(); i++){

    for (int j = i; j < records.size(); j++){

        if(j != i & isDuplicate(records.get(i), records.get(j))){

            Pair p = new Pair(records.get(i).RecID,records.get(j).RecID);

            duplicates.add(p);

        }

    }

}

我有一个数据库table，我想检查每条记录，所有记录只检查一次，以检查它们是否重复。

Answer 1

可以在 O(n) 中完成，方法是对第一个列表进行哈希处理并查看第二个列表以检查哈希集中是否有数据。两个循环都是o(n)。哈希查找是每个项目的 O(1)。

您的代码是 n**2，但这不是最有效的方法

重复检测算法的复杂性

complexity of a duplicate detection algorithm

java

complexity-theory