Какова сложность Big-O функции2?

Question

Я нашел эти две функции:

""" returns a list of the items in map """
def function1(map):
        a = list()
        for item in map:
            a.add(item)
        return a

""" hypothetical function """
def function2(map):
        b = list()
        for item1 in map.function1():
            for item2 in map.function1():
                if (xxxxx):
                   b.add(item2)
        return b

Я пытался определить сложность O для обеих этих функций. Я бы сказал, что function1 имеет O (n) сложность, а function2 имеет O (n ^ 2), но я не уверен насчет сложности function2, так как она вызывает function1 в каждом цикле.

Большое вам спасибо за ваш Помогите! : D

Answer 1

Функция2 будет O (n ^ 2). Да, функция1 имеет линейный размер карты, но также выполняет итерацию по значениям, что не позволяет ей стать O (n ^ 3) или O (n ^ 4).

Есть пара проблем однако с этим кодом вам нужно делать function1(map), а не map.function1(), поскольку function1 не является методом map. Кроме того, это может быть достигнуто в Python простым перебиранием элементов на карте следующим образом:

def function2(map):
    b = list()
    for item1 in map:
        for item2 in map:
            if (xxxxx):
                b.append(item2)
    return b

На самом деле это можно еще более упростить, используя понимание списка:

def function2(map):
    return [item2 for item1 in map for item2 in map if xxxxx]

Редактировать: обновлено понимание списка

Answer 2

Вы совершенно правы, что функция2 имеет O(n^2) сложность. Как вы заметили, он вызывает function1 в каждом цикле for для l oop. При вызове O(n) функции n раз она становится O(n^2)