检查数组中的重复项并删除它们最坏情况的复杂度是 O(n^2) 还是 O(n^3)？

Question

我正在尝试评估这个算法:

• 检查相等性的时间复杂度为 O(n²)

• 删除一个元素的时间复杂度为 O(n)

所以我认为整个算法在最坏的情况下将是O(n^3)。

    for (i = 0; i < ne-1; i++)
    {
        for (j = i+1; j < ne; j++)
        {
            if (strcmp(array[i].id, array[j].id)==0)
            {
                cont++;   

                for (k = j; k < ne - 1; k++)  
                    array[k] = array[k + 1];
                ne--;   
            }
        }
    }

Answer 1

尽管您认为比较的成本是 O(n²) 且删除元素的成本是 O(n) 是正确的，但这两个操作之间的相互关系会导致整个算法为 O(n²)。由于 O(n²) 位于 O(n³) 中，所以说该算法是 O(n³) 并没有不正确，但这不是一个严格的界限。

要了解原因，请考虑数组中某些元素所带来的成本。它将与每个后续元素进行比较(如 array[i] )，或者将其删除，涉及所有后续元素的移位。但不是两者皆有；一旦被删除，它就永远不会成为外循环中使用的元素。

无论哪种情况，元素的成本都是后续元素的数量，算法的总成本是最坏情况的 n(n-1)/2，即 O(n²)。 (如果删除元素，实际成本会更少；如果没有重复，最坏的情况就会发生。)

正如 @Amit 所指出的，如果执行比较或移动的成本不是 O(1)，则必须考虑到这一点，从而导致 O(n² m)，其中m 是比较或分配的成本。但认为该成本是固定的是正常的。

正如我在评论中指出的，所提供的算法是不正确的。正确的算法是:

for (i = 0; i < n - 1; ++i) {
    for (j = i + 1; j < n; ) {
        if (IsEqual(a[i], a[j])) {
            for (k = j; k < n - 1; ++k)  
                a[k] = a[k + 1];
            --n;   
        } else {
            ++j;
        }
    }
}

通常，更好的解决方案是对数组进行排序，这意味着相等的元素将相邻，然后执行一次 O(n) 传递来压缩结果；这是 O(n log n) (来自排序)，但不保留顺序。 (不过，您可以使用辅助数组来保留顺序。)