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

问：

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

我在两个相同类型的容器之间有一个相等运算符。我的算法遍历 （aka ） 并测试 中的项目包含。随后，该算法遍历 和 测试（又名 ）中的项目包含。在任何时候，如果 item 不在另一个中，则包含带有 .lhsthisrhsrhslhsthisbreaksfalse

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

我认为最大的复杂性是在边缘情况下，当包含测试对于两个元素和迭代的每个元素来说总是最后的。O(2n^2)lhsrhs

这是对的吗？我是否遗漏或误解了细微差别？

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

    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;
    }