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

Question

我正在做这个leetcode 问题，要求反转一个整数。我编写了这个方法，使用分而治之的递归技术将 int 转换为 string 并反转。我想知道这个时间复杂度是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 )。考虑这些成本不会改变整体分析。}