在递归函数中使用字符串的size()函数会导致很大的延迟/复杂性吗？

Question

我实现了一个递归函数的不同版本，该函数检查一个字符串是否是回文，并计算它们的复杂性，但对于将字符串大小作为参数传递或使用size()函数计算字符串并将其存储在函数内创建的变量中感到困惑，这样会更有效吗？

下面是该函数的两个版本的示例：

bool isPalindrome1 (string s) {
    int sz = s.size();            // size calculated and stored
    if (sz < 2) return true;
    return ((s[0] == s[sz-1]) && isPalindrome1(s.substr(1, sz-2)));
}

和,

bool isPalindrome2 (string s, int sz) {    //size passed as parameter
    if (sz < 2) return true;
    return ((s[0] == s[sz-1]) && isPalindrome2(s.substr(1, sz-2), sz-2));
}

第一个函数显然需要更多的时间“size()函数返回大小所需的时间”，但是如果原来的字符串大小有点大，这会不会有很大的延迟呢？这里的复杂性是如何计算出来的？

注意:我知道这不是递归检查字符串是否是回文的最有效方法，我只是想更好地理解复杂性和递归。

Answer 1

从C++11开始，std::string::size()就有了恒定复杂度。在此之前，它的复杂性被推荐为 (“应该”)是常数，而且我知道没有任何编译器不遵循此建议。

实际上，字符串大小值已经存储在string对象中，或者计算为两个存储指针之间的差异。