使用 isalnum() (Python) 的循环语句的时间复杂度

Question

如果我有这样一个 for 循环：

normalized_str = ''
for char in paragraph:
   if char.isalnum():
       normalized_str += char.lower()
   else:
       normalized_str += ' '

这基本上只是通过一个长段落字符串并连接所有单词并忽略标点符号（除此之外，仅作为概述）。

这个时间复杂度是O(n^2)吗？我相信 isalnum 函数的时间复杂度是 o(n)，因为它会遍历每个字符以检查它是否是字母数字，然后我们迭代 n 个单词。

由于在 for 循环的每次迭代中，我们都进行了一次 o(n) 操作，这是否使其成为 O(n^2)？或者只是 2 遍 O(n) 时间复杂度？

Answer 1

不，它仍然是 O(n)。如果它以某种方式检查自身，它只会是 O(n^2)。假设查找在一个哈希集中，查找时间为 O(1)。那么复杂度显然是O(n).

现在假设查找具有 O(n)，其中 n 是 alnums 本身。如果我答对了你的问题，它不会改变，这使它保持不变。所以整体复杂度也是 O(n)，因为它依赖于一个常数。

Time complexity of loop statement using isalnum() (Python)