performance - n元数组中未知元素的时间复杂度

Question

我是时间复杂性和算法的新手。

假设一个方法被传递给一个数组，我们只遍历该数组一次。我知道时间取决于数组的大小——我们称其为“n”。但是如果对于那个数组中的每个元素“el”，你都做了“el”次呢？在这种情况下，时间复杂度是多少，因为你有另一个变量？它仍然是“n”吗，因为在这种情况下我们只关心变量，即数组大小？

谢谢!

Answer 1

在这种情况下，时间复杂度是O(n*S)，其中S是数组中元素的平均值。

你可能想问:

Why the average and not max value?

嗯，时间复杂度实际上是:

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 是数组的总和)，并递增地填充其中的每个条目，导致 O(n *SUM) 解。

请注意，这通常被视为 pseudo polynomial复杂性，因为它在输入大小上并不是真正的多项式。