如果我可以将代码循环的次数减少一半，时间复杂度是否有任何变化

Question

我想知道如果我就地交换而不是循环遍历数组中的每个字符，我是否可以降低字符串反转函数的时间复杂度(大 O 表示法)。

我最初认为是的，因为进行就地交换我只需要遍历给定字符串中的一半字符。尽管再三考虑，这将给出 O(.5n) 的时间复杂度等于 O(n)，就像渐近复杂度一样，我们忽略了乘数。

public static String reverse(String str) {
char[] strArray = str.toCharArray();
for (int i = 0; i < str.length()/2; i++) {
char temp = strArray[str.length() - i - 1];
strArray[str.length() - i - 1] = strArray[i];
strArray[i] = temp;
}
return new String(strArray);
}

我可能已经回答了我自己的问题，因为我相信这将是相同的时间复杂性，就好像我遍历字符串中的每个字符，即 O(n)，但也许我错过了一些东西，我只是想要一些澄清。

Answer 1

你确实回答了你自己的问题。将所有输入的时间缩短一半不会改变理论时间复杂度。理论时间复杂度只是测量随着输入越来越大而运行的时间增长多少。而且您拥有的代码仍然需要两倍的时间，而输入的时间是两倍(因此，它是O(n))。