Какова временная сложность поиска буквы в строке?

Question

У меня есть строка с именем буквенно-цифровая, которая содержит все буквы и цифры.

alphanumeric = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"

Я хочу перебрать список отдельных символов (некоторые из которых являются буквенно-цифровыми, а некоторые просто пунктуацией), чтобы выяснить, какие из них являются буквенно-цифровыми. Какой будет временная сложность линии:

if character in alphanumeric:

? Я не был уверен, считаются ли строки списками для усложнения времени, потому что при просмотре вики Python (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|. Строка if c in alphanumeric then имеет временную сложность O(|alphanumeric|), если вы ищете c с помощью линейного поиска. Общая сложность всего алгоритма составляет O(|s|*|alphanumeric|). Однако, поскольку alphanumeric является константной строкой, ее длина также постоянна, и эту константу можно не учитывать: O(|s|) - сложность времени. В самом деле, асимптотическая сложность как функция размера ввода не зависит от длины постоянной строки или способа определения принадлежности.