检查字符串是否为回文的时间和空间复杂性
检查字符串是否为回文的时间和空间复杂性
提问于 2022-05-13 09:33:51
我想验证我关于JavaScript中有效回文函数的两个不同实现的时间和空间复杂性的假设。
在第一个实现中，我们使用一个助手函数，只传递指针。
const isPalindrome = str => {
return isPalindromeHelper(str, 0, str.length - 1);
}
const isPalindromeHelper = (str, start, end) => {
if (end - start < 1) return true;
return str[start] === str[end] && isPalindromeHelper(str, start + 1, end - 1)
}在这种情况下，我假设时间复杂度是O(N)，空间复杂度也是O(N)。
但是，假设不是传递指针，而是每次切分字符串。假设slice是O(n)运算。
const isPalindrome = str => {
if (str.length <= 1) return true;
if (str[0] !== str[str.length - 1]) return false;
return isPalindrome(str.slice(1, str.length - 1));
}如果切片是O(N)操作，这会将时间和空间复杂度都推到O(N^2)吗？时间因为时间的复杂性切片和空间会增加，因为我们不断地创建新的字符串？
回答 2
Stack Overflow用户
回答已采纳
发布于 2022-05-13 09:51:23
如果切片是O(N)操作，这会将时间和空间复杂度都推到O(N^2)吗？由于
slice的时间复杂性.
是的，，如果假设slice的时间复杂度为O()，则O(−1 +−2 +−3 +.+ 1)为O(2)
...and空间会增加，因为我们不断地创建新的字符串？
同样，如果假设为片分配了新的内存，那么我们就有(使用相同公式)O(2)的空间用法。
然而..。
由于字符串是不可变的，JavaScript引擎可能会从已经拥有字符串的内存中获益，而不会真正为片分配新内存。这叫做串实习。这将使时间和空间复杂性回到O()。但是，由于EcmaScript语言规范中没有实际这样做的要求，所以我们没有任何保证。
Stack Overflow用户
发布于 2022-05-13 09:39:59
它们都是递归操作，从0和n - 1开始一直运行到字符串(n)的整个长度，直到在n/2相遇为止。
在O表示法中，这意味着两者都是O(n)，因为您可以忽略常量2。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/72227397
复制相关文章
相似问题
腾讯云开发者
