java - 字符串反向操作最佳时间复杂度: Is it O(n) or O(n/2)?

Question

下面是字符串反转的代码片段

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)。

我想了解哪个实际上是字符串反转的正确时间复杂度。

任何见解都将真正有助于缓解这里的困惑。

Answer 1

O(n) 和 O(n/2) 之间没有什么区别。两者之间的差异是恒定的。

如果您想计算上述代码片段中操作的确切数量，则更准确地说是 3n/2，因为循环的每次迭代都包含 3 个操作。当然，您还必须将输入字符串转换为字符数组，反之亦然，这两者都需要线性时间。