python - 在字符串中查找字母的时间复杂度是多少？

Question

我有一个名为字母数字的字符串，其中包含所有字母和数字。

alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"

我想迭代单个字符的列表(其中一些是字母数字，一些只是标点符号)以找出哪些是字母数字。该行的时间复杂度是多少:

if character in alphanumeric:

是？我不确定字符串是否被视为时间复杂度的列表，因为在查看 Python wiki ( https://wiki.python.org/moin/TimeComplexity ) 时，操作“x in s”被视为 O(N)。

Answer 1

假设你的函数是这样工作的:

FindAlphaNumeric(s:string):string
1. alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"
2. result = ""
3. for each c:character in s
4.  if c in alphanumeric then result.append("1") else result.append("0")
5. return result

在本例中，有输入的长度 |s| 和常量字符串的长度 |alphanumeric|。如果您使用线性搜索来搜索 c，则 if c in alphanumeric then 行的时间复杂度为 O(|alphanumeric|)。整个算法的整体复杂度为O(|s|*|alphanumeric|)。但是，由于alphanumeric是一个常量字符串，所以它的长度也是常量，常量可以忽略不计:O(|s|)是时间复杂度。事实上，渐近复杂度作为输入大小的函数并不取决于常量字符串的长度，也不取决于确定成员资格的方式。