函数的大O时间复杂度

Question

试图找出函数的时间复杂度。你知道吗

功能是：

def test(self, alt):

    same = Sample()
    for i in self.items:
        if alt.func1(i):
            same.func2(i)

    return same

func1的复杂性为O（s），其中s是自身的大小。你知道吗

func2的复杂度为O（1）。你知道吗

如果func1是O（1），那么我知道它会是

O（1+n*n）=O（1+n^2）=O（n^2）

但是我需要用func1作为O（s）来解决这个问题

编辑：

我错了，我没有加上：

Sample()是O（1）

Answer 1

由于在for循环中的每次迭代中都调用func1，因此复杂性将取决于self.items、func1的长度和创建same实例的时间。你知道吗

因此，如果self.items的长度是n，而创建same的复杂度是x，那么总复杂度将根据以下公式计算：

x + ns

上述方程的复杂性取决于X，即如果X大于ns，则为O(x)，否则为O(ns)。一般来说，你可以这样写：

O(max{x, ns})

还要注意，如果func1是O（1），那么复杂性就不会像您所说的那样。那就是O(max{x, n})。你知道吗