我有一個以某種方式重新排列輸入串列并回傳輸出串列的函式。我對函式的時間和空間復雜度感到困惑。下面是代碼：
def rearrange_list(inp_list):
d = {}
output_list = []
for num in inp_list:
if num in d:
d[num] = 1
else:
d[num] = 0
output_list.append(num)
for k,v in d.items():
if v > 0:
for i in range(v):
output_list.append(k)
return output_list
這是我的復雜性分析：
- 時間復雜度： O(n m 2 ) 其中 n 是輸入串列的長度， m 是字典的大小
- 空間復雜度： O(n) 其中 n 是輸入串列的長度
我的主要困惑是我是否應該考慮遍歷字典 O(n) ，因為最壞的情況是串列中有 n 個專案，還是應該像我在分析中那樣用 m 表示它，因為它可以是任何來自0 到 n?
預先感謝您的幫助！
uj5u.com熱心網友回復：
你的時間和空間復雜度都是Theta(n). 雖然有時在時間或空間復雜度中包含不改變漸近值的術語可能有助于清晰（一個典型的例子是字串搜索演算法），但這在這里沒有多大意義。
雖然您對O(n m^2)時間復雜度的說法在技術上是正確的，因為 Big-O 表示法是一個上限，但您可以證明這O(n)也是一個上限，因為字典最多有大小，n我們只對每個鍵進行一次迭代：有n從輸入，最多n回圈迭代字典，以及n附加到輸出串列的專案。
如果需要，您可以計算所需的“輔助”空間，這將是所需的空間量，但不包括輸入或輸出陣列。在這里，那將是Theta(m)。但是，您應該注意，這種分析相當少見：假設，除非另有說明，否則空間復雜度分析將包括輸出的大小。
為了解決關于為什么第二個回圈仍然是具有許多重復值的線性時間的常見混淆，讓我們看一個示例。
有問題的行是：
for k, v in d.items():
if v > 0:
for i in range(v):
output_list.append(k)
假設我們的輸入串列是[1, 1, 1, 1, 1, 1, 1, 2, 2, 2]（總共十個元素：七個“1”和三個“2”）。
然后我們的dictionary.items()（每個元素的計數減一）看起來像：（[(key: 1, value: 6), (key: 2, value: 2)]它并沒有真正存盤為內部元組的 Python 串列，但這些是專案視圖物件的完整內容）。
讓我們逐行介紹第二個回圈的操作：
for k, v in [(key: 1, value: 6), (key: 2, value: 2)]:
# On our first iteration, so k = 1, v = 6.
if 6 > 0: # 1 operation
for i in range(6): # 6 operations
output_list.append(1) # 6 operations
# For the (k, v) pair of (1, 6), the inner-loop has run 6 times.
# Every time the inner-loop runs, the length of output_list
# increases by 1
# Second iteration of outer-loop runs again:
for k, v in [(key: 1, value: 6), (key: 2, value: 2)]:
# On our second iteration, so k = 2, v = 2.
if 2 > 0: # 1 operation
for i in range(2): # 2 operations
output_list.append(2) # 2 operations
# For the (k, v) pair of (1, 6), the inner loop has run 2 times.
# In total: 8 inner-loop iterations, and output_list has len 8
在非正式的復雜性分析中，“標準”的經驗法則是雙嵌套回圈的運行時間通常是二次的。這是因為我們正在計算內回圈迭代的總數，例如
for i in range(n):
for j in range(n):
作為
(n inner-loops per outer-loop) * (n outer-loops) = n^2 inner-loops
This assumption shouldn't be applied when the number of inner-loop iterations varies dramatically based on the state of the outer-loop. In our example, the inner-loop iterations is v, which depends on the outer loop.
To find the runtime here, we need a different way to count how many inner-loop iterations occur. Luckily, we can do that: in each inner-loop iteration, we append an element to output_list.
Since the final length of output_list is n, we know that the inner-loop has executed at most n times (technically, it's executed exactly n-m times, since the output_list already has size m after the earlier dictionary-initializing loop has terminated). Instead of incorrectly multiplying this by m, the number of outer-loop iterations, we should instead add the inner and outer loop iterations for a runtime of Theta(n m) which is Theta(n).
Addendum: Comments have correctly pointed out that since Python dictionaries don't have an O(1) amortized worst-case lookup/insert time guarantee, so the first loop is, at best, Omega(m*n). While Python uses pseudo-random probing on an open-addressing table, this only ensures good 'average' performance. Thanks to Kelly Bundy for the highly informative discussion and corrections.
Unfortunately, while O(1) amortized worst-case lookup/insert hashing is possible, for example with Cuckoo hashing, in practice this is significantly slower on average than what's currently used in most standard libraries, and is unlikely to change in the near future.
uj5u.com熱心網友回復：
逐步分解演算法：
- 第一個
for回圈 (for num in inp_list)。
它只是迭代串列，這需要O(N)時間，并且字典具有 sizeO(number of unique elements in list)，可以概括為O(N)空間（其中N= 串列長度 = 最大可能的唯一鍵數）。 - 第二個
for回圈（for k,v in d.items()）。
這會迭代 dict 中的鍵，這些鍵是O(number of unique elements in list)計數的。 - 第三個
for回圈（for i in range(v)）。
由于總和v只是串列中重復元素的計數，因此它的上限為O(N)。
演算法更好的近似應該是O(N)時間和空間，而不是提出的O(n m^2)
uj5u.com熱心網友回復：
時間復雜度
您可以將代碼分為兩部分。
第1部分
for num in inp_list:
if num in d:
d[num] = 1
else:
d[num] = 0
output_list.append(num)
在第一行中迭代inp_list，在每次迭代中呼叫if num in d. python 所做的是搜索字典的鍵d，因此這部分的時間復雜度是 O(nm)，其中 n 是 的大小，inp_listm 是 中唯一值數量的大小inp_list。
第2部分
for k,v in d.items():
if v > 0:
for i in range(v):
output_list.append(k)
在這一部分中，您將遍歷第一行中字典的大小，即 O(m)。我忽略了嵌套的 for 回圈，因為回圈可以替換為以下內容：
output_list = output_list [k] * v
發生在 O(1)
總之，時間復雜度應該是 O(nm m) = O (m(n 1)) = O(nm)。
盡管如此，由于 d 是一個字典，因此鍵搜索需要 O(1) 而不是 O(m)（請參閱此處的更多內容），從而使時間復雜度下降到 O(n)。
空間復雜度
由于創建了具有 m 個鍵的字典（其中 m 是 中唯一值的數量inp_list，因此空間復雜度為 O(n m) < O(2n) = O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446403.html
上一篇：什么資料結構最適合對字串集合進行快速查找和記憶體效率？
下一篇：JS中陣列的等邊