确定递归函数的复杂性

Question

我在确定以下代码的递归关系时遇到问题：

 public static void Method1(String S){ 
  if(S.length()>1){      
  System.out.print(S.charAt(S.length()-1));  
  Method1(S.substring(1,S.length()-1));
  System.out.print(S.charAt(0)); 
  } 
  if(S.length()==1) 
  System.out.print(S.charAt(0));
 }

我知道这段代码反转了给定的字符串，终止条件是string.length（）=0，但我不知道如何确定递归关系和复杂性。我应该考虑采取什么步骤来解决这类问题

Answer 1

您可以简单地将其重写为迭代，这不会改变复杂性。无论如何，考虑递归函数的单个调用：

不包括递归调用，它的复杂性是多少

对print()有两个带有第一个和最后一个字符的调用，或者在终止调用的情况下只有一个。其复杂性可能是恒定的。此外，对于递归调用的参数有一个substring()调用。这个调用可能是线性的，但也可能是常量，这取决于实现。

那么，每个调用有多少个递归调用

只有一个递归调用，这使得它非常简单。

此外，这种情况会反复出现多深

每个调用给下一个调用少两个字符，因此递归调用的数量与输入长度成线性关系。

摘要

对于整体复杂性，只需将不同的步骤相乘即可获得整体复杂性。在这种情况下，函数的作用非常糟糕。