如何在字符串中查找字母的时间复杂度是什么？

Question

我有一个名为字母数字的字符串，它包含所有字母和数字。你知道吗

alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"

我想遍历单个字符的列表（有些是字母数字，有些只是标点符号），找出哪些是字母数字。线路的时间复杂度是多少：

if character in alphanumeric:

是吗？我不确定字符串是否被认为是时间复杂度的列表，因为当查看pythonwiki（https://wiki.python.org/moin/TimeComplexity）时，操作“s中的x”被认为是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|)是时间复杂度。实际上，作为输入大小函数的渐近复杂性并不取决于常量字符串的长度，也不取决于成员身份的确定方式。你知道吗