下面的代码在内存方面的复杂性是多少？
我从 这里阅读了有关 Big-O 表示法的内容< /a> 对计算复杂性有几个问题。因此，对于下面的代码，我计算了复杂性。需要您的投入。
private void reverse(String strToRevers)
{
if(strToRevers.length() == 0)
{
return ;
}
else
{
reverse(strToRevers.substring(1));
System.out.print(strToRevers.charAt(0));
}
}
如果考虑内存因素，那么上述代码对于 n 个字符的字符串的复杂度是 O(n^2)。解释是对于由 n 个字符组成的字符串，下面的函数将被递归调用 n-1 次，并且每个函数调用都会创建一个单个字符的字符串（stringToReverse.charAT(0)）。因此，n*(n-1)*2 转换为 o(n^2)。让我知道这是否正确？
I read about Big-O Notation from here and had few questions on calculating the complexity.So for the below code i have calculated the complexity. need your inputs for the same.
private void reverse(String strToRevers)
{
if(strToRevers.length() == 0)
{
return ;
}
else
{
reverse(strToRevers.substring(1));
System.out.print(strToRevers.charAt(0));
}
}
If the memory factor is considered then the complexity of above code for a string of n characters is O(n^2). The explanation is for a string that consists of n characters, the below function would be called recursively n-1 times and each function call creates a string of single character(stringToReverse.charAT(0)). Hence it is n*(n-1)*2 which translates to o(n^2). Let me know if this is right ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
差不多：是
n * (n-1) / 2，而不是*2，这也是 O(n^2)。请注意，o(n^2)（小-O）意味着其他< /a>，所以区分很重要。这是假设我们将其视为伪代码。特定于语言的实现和智能编译器可能能够显着提高运行时间。例如，可以观察到您只是反转字符串的编译器可能只是执行就地反转，即 O(n)。
Almost: it's
n * (n-1) / 2, not*2, which is also O(n^2). Note that o(n^2) (little-O) means something else, so the distinction is important.This is assuming we're considering this as pseudocode. Language-specific implementations and smart compilers may be able to improve the running time substantially. For instance, a compiler that can observe that you're simply reversing the string might just do an in-place reverse, which is O(n).
看起来像 Java，所以它不是 O(n**2)。这是因为字符串共享底层字符序列缓冲区；他们可以做到这一点，因为它们是不可变的对象。
但在栈空间中却是O(n)。那不好。最好分配一个可变的字符工作缓冲区，将字符串反转为该缓冲区，然后立即打印全部内容。
Looks like Java, so it's not O(n**2). That's because strings share the underlying character sequence buffers; they can do this because they are immutable objects.
But it is O(n) in stack space. That's not good. It's better to allocate a mutable working buffer of characters, reverse the string into that, and then print the whole lot at once.