以下代码在内存方面的复杂程度如何？

我从here读了Big-O符号，并且在计算复杂度方面几乎没有问题。因此，对于下面的代码，我计算了复杂度。需要你的投入相同。以下代码在内存方面的复杂程度如何？

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）。让我知道如果这是正确的？

来源

2010-03-28 Cshah

因此，它是n *（n-1）* 2，其转换为o（n^2）。让我知道如果这是正确的？

差不多：它是n * (n-1)/2，而不是*2，这也是O（n^2）。请注意，o（n^2）（little-O）means something else，所以区别很重要。

这是假设我们正在考虑这是伪代码。特定于语言的实现和智能编译器可能能够大幅缩短运行时间。例如，一个可以观察到你简单地反转字符串的编译器可能只是做一个就地反转，即O（n）。

来源

2010-03-28 13:40:11

@John：对，它应该是n *（n-1）/ 2 – Cshah 2010-03-28 14:23:55

看起来像Java，所以它的不是 O（n ** 2）。这是因为字符串共享底层的字符序列缓冲区;他们可以做到这一点，因为他们是不可变的对象。

但它是堆栈空间中的O（n）。这不好。最好分配一个可变的工作缓冲区，将字符串反转为该字符串，然后一次打印整个批次。

来源

2010-03-28 13:46:06

+1。 'System.out'和其他小东西指向它是Java，'substring'不会复制原始的'String'字符数组。这是'String（String）'构造函数的一个原因。 – Phil 2010-03-28 13:55:00

为了举例，不要考虑在java中子字符串共享底层字符序列的事实。假设每次为新字符串分配一个内存。 – Cshah 2010-03-28 14:20:09

以下代码在内存方面的复杂程度如何？

回答

相关问题