字符串反转的时间复杂度：反转操作的时间复杂度是否为O(n)？

Great question—let’s unpack this clearly and directly.

The short answer: Yes, string reversal has a time complexity of O(n). This aligns perfectly with your observation that longer strings require more work to reverse. Here’s the breakdown:

At its core, string reversal requires handling every character in the string at least once. The standard approach uses a two-pointer technique: start with one pointer at the start of the string and another at the end, swap the characters at these positions, then move the pointers toward the center until they meet.

Each swap is an O(1) operation, and you’ll perform roughly n/2 swaps (where n is the length of the string). Since Big O notation ignores constant factors, n/2 simplifies to O(n)—the number of operations scales directly with the input size.

For example, here’s a straightforward manual implementation of string reversal in Python:

def reverse_string(s):
    s_list = list(s)
    left, right = 0, len(s_list) - 1
    while left < right:
        # Swap characters at the two pointers
        s_list[left], s_list[right] = s_list[right], s_list[left]
        left += 1
        right -= 1
    return ''.join(s_list)

Even if you use built-in methods (like Python’s s[::-1]), the underlying logic follows this linear pattern—every character gets processed once to build the reversed string.

A quick edge case note: In languages where strings are immutable (like Java or Python, where modifying a string creates a new object), you might think there’s extra overhead. But even then, you still need to iterate through all n characters to construct the reversed version, so the time complexity remains O(n).

To circle back to your original point: The fact that longer strings demand more work is exactly what defines linear time complexity. As n grows, the number of operations grows proportionally—no more, no less.

内容的提问来源于stack exchange，提问作者user9352220