计算我的函数的大 o

Question

我正在学习大 O，需要一些帮助来计算我的函数的大 O。

如果 self 的大小为 s 而 other 的大小为 o，我需要找出大 O

我不确定调用 has 函数的复杂性，因为我知道相交处的 for 循环将是 S 的复杂性

但是 has() 的复杂度会是 o 吗？正如我想象的那样，它必须循环遍历 o 直到找到匹配项或 returns false.

正在使用的self和other的数据类型是正整数和负整数

 def has(self, item):

        return item in self.items

    def intersection(self, other):
        common = Set()
        for item in self.items:
            if other.has(item):
                common.add(item)
        return common

Answer 1

检查值是否在列表中的时间复杂度为 O(n)（它必须循环）。检查值是否在集合中的时间复杂度为 O(1) - 它将计算一个散列并检查集合中是否存在该散列的值。您可以编写自己的 class 实现 in，其中时间复杂度与您自己的实现相关。如果不知道 other.

的定义，您将无法回答这个问题

计算我的函数的大 o

calculating big o of my function

python

algorithm

big-o