c++ - 两个容器之间的相等运算符的时间复杂度是多少？

Question

我正在测试我对复杂性的理解，并想验证我的答案。

我在两个相同类型的容器之间有一个相等运算符。我的算法遍历lhs(aka this) 并测试rhs. 随后，该算法迭代rhs并测试lhs(aka this) 中的项目包含情况。在任何时候，如果 item 不在 other 中，则包含breaks带有 a的算法false。

所以，我认为最小复杂度是常数时间O(1)，因为当lhs和rhs大小不同时，结果是错误的。

我认为最大的复杂性是O(2n^2)针对边缘情况，即对于两个lhs和rhs迭代的每个元素的包容性测试始终是最后一个。

这是正确的吗？是否有我遗漏或误解的细微差别？

这是我的算法的实现。它们是自定义类型，但算法应该是可读的。

    bool LibrdfModel::operator==(LibrdfModel &rhs) {
        /**
         * Note on complexity - this algorithm is quite expensive.
         * First, if not same size, then return false. So the rest is assuming the size of lhs and rhs are equal.
         * iterate over lhs. For each of the n elements element we search through n rhs --> n^2
         * Then we iterate over rhs. For each of the n elements we search through n lhs elements --> n^2
         * So we have O(2n^2)
         */

        // we first try comparing size. If they are not equal, then the models are not equal
        if (size() != rhs.size())
            return false;

        // if they are the same size, we need a more expensive operation to compare the models
        // No equals operator exists for a model so we use this strategy:
        // Convert this and that to a stream. Iterate over each stream
        // checking if all statements in this are in that and all
        // statements in that are in this. Then this == that.
        bool all_this_in_rhs = true;
        bool all_rhs_in_this = true;
        LibrdfStream this_stream = toStream();
        {
            int count = 0;

            while (!this_stream.end()) {
                LibrdfStatement statement = this_stream.getStatement();
                // check statement is in other model
                bool contains_statement = rhs.containsStatement(statement);
                if (!contains_statement) {
                    all_this_in_rhs = false;
                    break;
                }
                this_stream.next();
                count++;
            }
        }

        LibrdfStream rhs_stream = rhs.toStream();
        {
            int count = 0;
            while (!rhs_stream.end()) {
                LibrdfStatement statement = rhs_stream.getStatement();
                // check statement is in other model
                bool contains_statement = rhs.containsStatement(statement);
                if (!contains_statement) {
                    all_rhs_in_this = false;
                    break;
                }
                rhs_stream.next();
                count++;
            }
        }
        return all_this_in_rhs && all_rhs_in_this;
    }

标签： c++algorithmtime-complexitycomplexity-theoryequality