Как временная сложность приведенного ниже кода Python вычисляется как 0 (n log n)? - PullRequest
Новая
       9

Как временная сложность приведенного ниже кода Python вычисляется как 0 (n log n)?

0 голосов
/ 27 мая 2019

Я понял, как работает вычисление Big O, после просмотра нескольких видео, когда я начал практиковать несколько проблем, я пришел к этому коду, где, как мне кажется, сложность времени кода равна O (n ^ 2), потому что внешний цикл будет запускаться O ( n) и внутренний цикл также будет запускаться O (n). Потому что внутренний цикл должен перебирать весь список, чтобы найти уникальное имя. Но блог объясняет это как O (n log n). Как? 

def list_unique_names(phonebook):
    unique_names = []
    for name, phonenumber in phonebook:             # 1
        first_name, last_name = name.split(" ", 1)
        for unique in unique_names:                 # 2
            if unique == first_name:
                break
        else:
            unique_names.append(first_name)
    return len(unique_names)

phonebook = [
    ("John Doe", "555-555-5555"),
    ("Albert Einstein", "212-555-5555"),
    ("John Murphey", "202-555-5555"),
    ("Albert Rutherford", "647-555-5555"),
    ("Elaine Bodian", "301-555-5555"),
]

Я ожидаю, что сложность равна O (n ^ 2), но владелец блога говорит, что это O (n log n).

1 Ответ

1 голос
/ 27 мая 2019

Вы правы, код, который вы опубликовали, выполняется в O(n^2).

С помощью set вы можете выполнить ту же операцию в amortized O(n): 

def list_unique_names(phonebook):
    unique_names = set()
    for name, phonenumber in phonebook:
        first_name, _ = name.split(" ", 1)
        unique_names.add(first_name)
    return len(unique_names)
...