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

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，其中M是数组中最大的名称，这是不正确的(它在定义上界是正确的，但上界不紧，所以不是很有趣；在同样的意义上，N^2xM^2是正确的)。

我认为在许多实际感兴趣的案件中，你的分析是不正确的。字符总数等于字符串数，乘以每个字符串的平均字符数，即字长(注:平均值，而不是最大值！)。当字符串的数量变大时，平均样本字长将接近您要抽样的任何分布的平均值。因此，至少对于采样是iid的任何行为良好的分布，时间复杂度只是N。

一个很好的实用示例是存储名称的数据库。当然，这取决于数据库中的人，但是如果你存储的是美国公民的名字，那么当N变得很大时，在美国，内部操作的数量将接近一个名字中字符平均数的N倍。后一个量根本不依赖于N，所以它在N中是线性的。