# find all possible sorted substrings of s
substr = ["".join(sorted(s[i: j]))
for i in range(len(s))
for j in range(i 1, len(s) 1)]
我知道這個sorted()方法是 O(nlog(n))，所有可能的子串的發現是 O(n^2)。然而，這.join()就是讓我失望的原因。sorted()回傳一個串列并.join()遍歷串列中的每個元素以將其附加到一個字串中。所以它應該是一個線性操作。
因此，對于嵌套回圈，我的子字串排序器是否為 O(n^2) * O(nlogn) 用于對每個結果進行排序 * O(n) 用于連接？因此 O(n^4logn)??
如果是這樣，拆分操作會使這更有效嗎？我有另一個實作，我將子字串的排序移動到第二個串列理解
substr = [s[i: j] for i in range(len(s))
for j in range(i 1, len(s) 1)]
sortedSubstr = ["".join(sorted(s)) for s in substr]
這將使它成為 O(n^2) 串列理解第一 O(n)*O(nlogn) 用于第二個串列理解
現在制作整體程式 O(n^2logn)
如果我錯了，請糾正我。謝謝
uj5u.com熱心網友回復：
為了分析起見，讓我們用檔案中描述的等效回圈替換推導式。
你的第一個方法變成
substr = []
for i in range(len(s)): # O(n)
for j in range(i 1, len(s) 1): # O(n)
substr.append("".join(sorted(s[i: j]))) # O(n*logn)
# Overall O(n^3 * logn)
請注意，這substr.append("".join(sorted(s[i: j])))不是乘法，而是以下操作的順序組合（沒有實際分配發生）
temp = s[i:j] # O(j-i), which worst case we can take O(n)
sorted_temp = sorted(temp) # O(n*logn)
joined_temp = "".join(sorted_temp) # O(n)
substr.append(joined_temp) # amortized O(1)
# Overall O(n*logn)
現在在第二種方法中，代碼變成
substr = []
for i in range(len(s)): # O(n)
for j in range(i 1, len(s) 1): # O(n)
substr.append(s[i:j]) # O(n) for the slice
# first loop: O(n^3)
sortedSubstr = []
for s in substr: # O(n^2), we have appended n^2 times in the first loop
sortedSubstr.append("".join(sorted(s))) # O(n*logn)
# second loop: O(n^3 * logn)
# Overall O(n^3 * logn)
如您所見，它們應該具有相同的時間復雜度。我幾乎錯過了substrlength isn^2而不是n，所以這可能是一個陷阱。
各種操作的時間復雜度參考：
- 字串切片的時間復雜度
- 為什么python的list.append()方法的時間復雜度是O(1)？
uj5u.com熱心網友回復：
對于第一個演算法，時間復雜度是O(n^3*log(n))，因為在兩次回圈之后，您不會join為sorted. 您分別排序和加入。所以O(n) O(n*log(n)) = O(n*log(n))，乘以O(n^2)（嵌套回圈）給我們O(n^3*log(n))。
關于第二種演算法。
- 的計算
substr給我們O(n^3)：同樣O(n^2)的嵌套回圈乘以O(n)切片s。 - 請注意，
len(substr)是O(n^2)-每個(i, j)從嵌套回圈。 - 的計算
sortedSubstr給了我們O(n^3*log(n))：對于我們呼叫的substr（其計數是O(n^2)）的每個元素sorted。每個元素的lenisO(n)，所以sorted(s)給了我們O(n*log(n))。所以，同樣，O(n^2) * O(n*log(n)) = O(n^3*log(n))。 - 的計算
substr（O(n^3)）加的計算sortedSubstr（O(n^3*log(n))）的產率O(n^3*log(n))。
所以O(n^3*log(n))第二個也是一樣。
uj5u.com熱心網友回復：
在這個運算式中：
"".join(sorted(s[i: j]))
O(n)join可以忽略不計，因為在完成 O(nlogn) 之后，您只做了一次sort。
O(nlogn n)= O((n 1)logn)=O(nlogn)
做那種 n^2 次會讓你得到O(n^3 logn)，不管你是否/何時做join.
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/397533.html