这个算法有三个嵌套循环 O(m*n) 还是 O(m*n^2)？

Question

我正在为 funzies 进行代码挑战，并尝试确定我的解决方案的时间复杂度。大学毕业已经有一分钟了，所以我想确认我的分析是否正确。这是代码（我已尽力概括它，以便与实际问题的细节无关，因此它更多是伪代码）。该文件是一个基本文本文件，其中的字符串由换行符分隔。每条线的长度相同，因此可以将其概念化为网格。在此分析中，令 m=#lines（行）和 n=#characters per line（列）。

currRow = 0
for line in file:
    for match in re.finditer(r"\d+", line):
        for i in range(match.start(), match.end()):
            print(currRow, i) // placeholder, the actual logic i'm checking here is irrelevant
    currRow += 1

我试图确定时间复杂度是 O(mn) 还是 O(mn²)

最外面的循环迭代了 m 次，因此这部分很容易弄清楚。我对两个最里面的循环及其关系感到困惑。我使用的正则表达式是贪婪的，因此它将搜索可能的最长数字子串（例如 123abc4567 只会返回 123 和 4567 的匹配，而不是更小的子匹配，例如 23 或 56）。尽管如此，完全分开来看，很容易看出每个循环可以相对于n增长（在第一个循环的情况下，您仍然可以有最多n/2个匹配，对于第二个循环，您可以有一个匹配，并且因此必须遍历字符串中的每个索引）。由于它们是嵌套的，这可能意味着复杂度为 O(n²)。但我的直觉告诉我，这些循环是相互关联的，事实上，当作为一个整体时，它们受到 O(n) 的约束，而且我无法想象实际会发生 n^2 次操作的情况。

我是这么想的：外循环迭代所有匹配项，因此 #matches 操作。内部循环对每个索引中的每个索引进行操作。但由于贪婪的正则表达式，这些匹配的最大可能是 (n / #matches)，因为子字符串必须有自己的字符。因此，这些循环的组合复杂度可以归类为#matches * (n / #matches) = n。即使我们假设 #matches 受到限制（不能有比字符更多的匹配项），我们也可以声明 O(n) * O(n/n)，它仍然是 O(n)，渐近地。

这是正确的吗？还是我的直觉错了？

Answer 1

你的直觉是正确的。

如果匹配的数量为

k

，并且匹配的长度分别为

n1

、

n2

、

n3

、...、

n_k

，则

的复杂度

for match in matches:
    for i in range(match.start(), match.end()):
        do_one_operation()

是总和

n1 + n2 + ... + n_k

。

假设匹配不重叠（你必须证明这一点！！），这个总和最多等于该行中的字符数。

但是，有一些注意事项。

re.finditer

的复杂性

当您在

re.finditer

上调用函数

line

时，该函数将在内部执行循环以查找匹配项。这个循环显然至少是 O(n)，但也许甚至更多。您必须查看

re.finditer

的文档才能确定。

令人高兴的是，在

re.finditer

循环实际开始之前，

for match in ...

在整条线上仅被调用一次，因此您的总复杂度将为

O(m * ((complexity of finditer) + complexity of inner loop))

。如果

finditer

的复杂度为 O(n^2)，那么即使内循环仅为 O(n)，您的总复杂度也将为 O(m n^2)。

在内循环中所做的事情的复杂性

你写道：

print(currRow, i) // placeholder, the actual logic i'm checking here is irrelevant

这实际上是相关的。到目前为止，您唯一证明的是这里编写的操作将执行 O(m n) 次。但如果这个操作本身的复杂度大于 O(1)，那么你的代码的总复杂度将大于 O(m n)。

请注意，当表达复杂性时，我们通常会宣布我们正在计算的内容。复杂度是的数量。当谈论比较排序的复杂性时，我们通常会计算比较的次数。如果您没有明确指定您正在计算的操作，那么读者会假设您正在计算的操作有点“基本”，但如果实际上在内部循环中执行的操作是一个缓慢的操作（例如本身包含一个循环），然后说你的代码复杂度为 O(m n) 是骗人的。