反转字符串：这是 O(log n) 时间复杂度吗？

Question

我在做 this leetcode 题，要求反转整数。我编写了这个方法来将 int 转换为字符串并使用分而治之递归技术进行反转。我想知道这是 O(log n) 时间复杂度吗？（n 是字符串中的字符数）。

def __reverse_recur__(self, num: str):
    N = len(num)
    # if we are reduced to only a single char, return it
    if N == 1:
        return num
    else:
        n = int(N / 2)  # index to split string from middle
        
        # concatenate the recursion result as follows:
        # recurse on the right-part of the string to place it as the left half of the concatenation
        left_half = self.__reverse_recur__(num[n:])
        # recurse on the left-part of the string to place it as the right half of the concatenation
        right_half = self.__reverse_recur__(num[:n])

        # return the concatenated string
        return left_half + right_half

Answer 1

不是，是O(n log n) .

字符串连接是线性的。表达式 left_half + right_half 中的每个 + 需要 O(l+r ) 时间，其中 l = len(left_half) 和 r = len(right_half).

您将两个长度为 n/2 的字符串连接 1 次。
您将两个长度为 n/4 的字符串连接 2 次。
您将两个长度为 n/8 的字符串连接 4 次。
...
您将两个长度为 4 的字符串连接 n/8 次。
您将两个长度为 2 的字符串连接 n/4 次。
您将两个长度为 1 的字符串连接 n/2 次。

每一步需要 O(n) 并且有 O(log n) 个步骤，导致总时间复杂度为 O(n log n).

_{脚注：字符串切片 num[n:] 和 num[:n] 也具有线性复杂度。创建长度为 k 的切片是 O(k)。考虑这些成本不会改变整体分析。}

反转字符串：这是 O(log n) 时间复杂度吗？

Reversing a String: Is this O(log n) time complexity?

python

string

algorithm

time-complexity

reverse