algorithm - 如何计算可变长度的嵌套循环的运行时复杂度

Question

假设我有一个任务要编写一个算法来遍历字符串数组并检查数组中的每个值是否包含 s 字符。该算法将有两个嵌套循环，这是伪代码:

for (let i=0; i < a.length; i++)
  for (let j=0; j < a[i].length; j++)
      if (a[i][j] === 'c')
         do something

现在，任务是确定算法的运行时复杂性。这是我的推理:

令数组中的元素个数为n，而字符串值的最大长度为m。所以复杂度的一般公式是

n x m

现在是可能的情况。

如果字符串值的最大长度等于元素的数量，我得到复杂度:

n^2

如果元素的最大长度小于元素个数a，则复杂度为

n x (n - a) = n^2 - na

如果元素的最大长度比元素个数多a，则复杂度为

n x (n - a) = n^2 + na

由于我们丢弃了较低的增长函数，因此算法的复杂度似乎为 n^2。我的推理是否正确？

Answer 1

你的时间复杂度就是字符总数。哪种分析适用，完全取决于您对单词长度和单词数量之间关系的假设是否成立。请特别注意，您所说的时间复杂度为 N x M，其中 M 是数组中最大的名称，这是不正确的(从某种意义上说，它是正确的，因为它设置了上限，但上限并不严格，所以它是不是很有趣；它是正确的，就像 N^2 x M^2 是正确的一样)。

我认为在许多实际案例中，您的分析肯定是不正确的。字符总数等于字符串数乘以每个字符串的平均字符数，即字长(注意:平均值，不是最大值!)。随着字符串数量变大，平均样本字长将接近您从中采样的任何分布的平均值。因此，至少对于采样为 iid 的任何表现良好的分布，时间复杂度仅为 N。

一个很好的实际例子是一个存储名字的数据库。这当然取决于哪些人碰巧在数据库中，但是如果你正在存储美国公民的名字，那么当 N 变大时，内部操作的数量将接近名字中平均字符数的 N 倍，在我们。后一个数量根本不依赖于 N，因此它与 N 成线性关系。