時間複雜度（帶有元素列表）

出於好奇。假設我有一個包含N個元素（將重複）的列表以及一個將返回這些元素頻率的函數。我認爲這個計劃的時間複雜性應該是O（N）是對的？由於函數只需循環遍歷N並檢查元素是否已經存在，如果是，+ =，else = 1。好的，所以我和我的朋友有一個論點，如果我們需要多元化它的頻率呢？也許除以它的總數？我的朋友認爲複雜度應該是O（N^2），但它聽起來並不適合我。你怎麼看，爲什麼？時間複雜度（帶有元素列表）

謝謝。

來源

2017-03-16 USER1223_T

這取決於你將如何記錄的頻率。如果你將使用一個數組，他們對於每個+ =你需要先找到前一個頻率值，這個複雜度是二次的。但是，如果您維護一個散列表結構，平均訪問時間是即時的，則複雜度將是線性的。

來源

2017-03-16 14:59:38 infiniteRefactor

如果我們使用哈希表，複雜度仍然是O（N）？即使列表數量巨大，並且需要將其頻率（對於每個元素）也乘以？ –

如果項目數量巨大，您可以分配一個巨大的散列表，以便表擴大不是問題，並且散列衝突很少。如果您需要對結果進行額外計算，這是一個不同的問題，您應該更具體地說明您想要做什麼。例如，如果要將頻率與列表中的值相乘，則需要迭代散列表的鍵並將其與值相乘。這將是第二步，總複雜性仍然是O（N）。 – infiniteRefactor

我明白了，非常感謝你的明確解釋！ –

時間複雜度（帶有元素列表）

回答

相關問題