下面是字符串反转的代码片段
private static String reverseString(String originalString){
char arr[]= originalString.toCharArray();
char temp;
for(int i= 0,j=arr.length-1;i<(arr.length/2);i++,j--){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
return new String(arr);
我看到很多关于上述字符串反转的时间复杂度的讨论，其中一些提到复杂度为 O(n/2) 和一些 O(n)。
我想了解哪个实际上是字符串反转的正确时间复杂度。
任何见解都将真正有助于缓解这里的困惑。
最佳答案
O(n) 和 O(n/2) 之间没有什么区别。两者之间的差异是恒定的。
如果您想计算上述代码片段中操作的确切数量，则更准确地说是 3n/2，因为循环的每次迭代都包含 3 个操作。当然，您还必须将输入字符串转换为字符数组，反之亦然，这两者都需要线性时间。
关于java - 字符串反向操作最佳时间复杂度: Is it O(n) or O(n/2)?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31109959/