Python - Big (O) Runtime: понимание списка и цикл

Question

В CTCI (версия Python) время выполнения приведенного ниже кода описывается как O (N)

# O(N)

def unique(string):
    # Assuming character set is ASCII (128 characters)
    if len(string) > 128:
        return False

    char_set = [False for _ in range(128)]
    for char in string:
        val = ord(char)
        if char_set[val]:
            # Char already found in string
            return False
        char_set[val] = True

    return True

Это действительно смущает меня, когда я вижу понимание списка в формировании char_setи еще один цикл for сразу после ... не должно ли время выполнения быть O (N ^ 2)?

Редактировать: Я также запутался, почему Laakman использует len (string)> 128 для проверкидля ascii char.Разве это не даст длину рассматриваемой строки, а не символьное значение, которое дает метод ord в Python?

Edit1: можно ли добиться того же, если она не использует val = ord(char)?Это изменит следующую строку на if char_set[char]:

Answer 1

Ваш второй вопрос заключается в том, что этот код предназначен для проверки того, что каждый символ в строке уникален.Предполагая, что строка ASCII, если она длиннее 128 символов, она не может содержать только уникальные символы, поскольку в кодировке ASCII только 128 символов.

Answer 2

Количество времени, которое занимает [False for _ in range(128)], фиксировано и поэтому имеет временную сложность O(1).