计算时间和 space 复杂度时遇到问题？

Question

题目是检查两个字符串是否相互旋转。所以，这是我为此编写的函数：

 bool areRotations(string s1, string s2)
        {
            int n1 = s1.length(), n2 = s2.length();
            if (n1 != n2) return 0;
            s1 += s1;
            if (s1.find(s2) != string::npos)
                return 1;
            else
                return 0;
        }

我刚刚检查了s1+s1中是否存在s2，如果存在，则s1和s2一定是互为旋转

我无法计算出我的代码的时间和space复杂度。我能理解的是它应该是 O(n) 时间复杂度因为首先要将 s1 连接到 s1，我们必须创建 s1 的副本，还要在 s1 中找到 s2，我们必须遍历，因此时间复杂度为 O(n)。同样对于 space，它应该是 O(n)，因为我们正在制作 s1 的副本。 这是正确的吗？

Answer 1

I am not able to figure out the time and space complexity of my code. [...] Is this correct?

std::string::length 运行s 恒定时间 (since C++11)。线性时间的比较和串联运行。但是整个算法可以在非线性时间内运行。

事实上，C++ 标准实际上并不要求任何特定算法或保证 std::string::find 的复杂性。因此，不可能独立于您使用的 STL 实现给出答案。如果实现是天真的或使用著名的 Boyer-Moore 算法，则最坏情况下的时间复杂度可能是 O(n^2) 在您的情况下（其中 n 是输入字符串的大小）。对于 s1="aaaaaaaaaca" 和 s2="aaaaaaaaaac" 这样的输入，可能会发生这种情况。尽管 std::search provide stronger guarantees, it does not provide any search algorithm running in linear-time. To ensure a linear-time complexity, you can use the KMP search algorithm (or better variants like the 2-way string-matching algorithm).

因此，使用 KMP 算法，您的解决方案的时间复杂度和 space 将为 O(n)。这是最佳的，因为需要读取输入字符串并将其存储在某处（至少在您的实现中）。

计算时间和 space 复杂度时遇到问题？

Problem figuring out time and space complexity?

c++

performance

time-complexity

space-complexity