这个函数的复杂度是什么？

Question

我正在Codeacademy上练习，需要编写以下函数：

定义一个名为anti_vowel的函数，它接受一个字符串text作为输入，并返回删除所有元音字母后的文本。

这是我的解决方案：

def anti_vowel(text):
md = ""
for ch in text:
    if ch not in "aeiouAEIOU":
        md =  md + ch
return md 

它的表现很好，但我想知道这个函数的复杂度。我认为它是 O(nk)，其中 n：="文本长度"，k：="aeoiuAEIOU 的长度"。我拿出一个文本元素并将其与所有元音字母进行比较，这需要花费 O(k) 时间。但我重复这样做 n 次，所以总共需要 O(nk) 的时间。我的分析正确吗？我该如何改进此函数？它是否可以达到线性时间复杂度？

- GniruT

---

请注意，缩进不正确，如图所示。我假设您的实际代码已经正确缩进。 - Tom Zych

Answer 1

大 O 复杂度并不是这样计算的。 k（元音字母的长度）是一个常数，它不会根据输入的长度而改变。因此，在计算复杂度时我们要将其排除。

你的函数只是 O(n)，即线性复杂度。

- Daniel Roseman

Answer 2

你是对的，你的函数复杂度为O(nk)。你忽略的是，如果k是一个不等于零的常数，O(nk)等于O(n)。这意味着你的函数已经在线性时间内运行。

你正在迭代一个具有n个字符的字符串text。每次迭代，你都会检查当前字符是否在一个固定长度为k（k是一个常数！）的字符串中。最坏情况下，这个检查将需要k步。

因此，你的复杂度为：
O(k)O(n) = O(kn) = O(n) 我建议你阅读一下复杂度类的基本属性，特别是它们的和、积以及乘以一个常数的工作方式，可以在这里了解更多信息。

- timgeb