函数2的Big-O复杂度是多少？

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的复杂度，因为它在每个for循环中都调用function1。

非常感谢您的帮助！ ：D

Answer 1

您完全正确地认为function2具有O(n^2)复杂度。如您所述，它在for循环的每个循环中都调用function1。通过调用O(n)函数n次，它变为O(n^2)

Answer 2

Function2将为O（n ^ 2）。是的，function1在映射的大小上是线性的，但是也在迭代这些值，从而防止了将其变为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]

编辑：更新列表理解