n元素陣列中未知元素的時間複雜度

Question

我是時間複雜性和算法的新手。

說一個方法傳遞一個數組，然後我們遍歷該數組一次。我知道時間取決於數組的大小 - 我們稱之爲「n」。但是如果對於數組中的每個元素「el」，你會做「el」次？這種情況下的時間複雜度是多少，因爲你有另一個變量？它仍然是「n」，因爲我們只關心這種情況下的變量，這是數組的大小？

謝謝！

Answer 1

在這種情況下，時間複雜度爲O(n*S)，其中S是數組中元素的平均值。

您可能要問：

爲什麼平均，而不是最大值？

好了，時間複雜度居然是：

T = arr[1] + arr[2] + ... + arr[n] = (arr[1] + arr[2] + ... + arr[n])/n *n = 
    = S *n 

最後一個等式是真實的，因爲(arr[1] + arr[2] + ... + arr[n])/n=S由平均定義。

---

，其中類似看到的東西是對於Partition Problem動態規劃溶液一個常見的例子中，將創建大小SUM/2 * n（其中SUM是陣列的總和）的2維陣列，和填充每個逐步進入，造成O(n*SUM)解決方案。

請注意，這通常被認爲是pseudo polynomial的複雜性，因爲它在輸入大小上並不是真正的多項式。

Answer 2

N通常用於表示問題的大小，對於這樣的問題，通常是數組的大小。如果我們將每個元素的內容視爲一個數字，那麼該數字的最大值就是數字，所以我們認爲它是一個常數，並且它在最終的複雜度表達式中不起作用。