我正在做這個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
uj5u.com熱心網友回復：
不，它是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 )。考慮這些成本不會改變整體分析。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/411527.html
標籤：