这个setitem方法的Big-O是什么？

Question

此 __setitem__ 空字典方法的时间复杂度是多少？我认为，字典的 .key 和 .value python 方法是 O(n)（我在某处读过），for 循环也是 O(n)。我的猜测是 O(n)*O(n)*O(n)+O(1) = for loop + if + if body + append。但是我不确定那种 "if in for loop body" 的情况以及 .item 和 .value 是 O(n)。

请帮忙。这是在我的学校考试中。代码在 python.

def __setitem__(self,k,v):
  for item in self._table:
    if k == item._key:
      item._value = v
      return
  self._table.append(self._Item(k,v))

Answer 1

是O(len(self._table))（假设构造self._Item是O(1)）因为在最坏的情况下你需要检查self._table对象中的每个元素。

if 语句及其主体在输入方面都是 O(1)，因为它们是原子操作。因此，for 循环的复杂度为 O(n) * O(1) * O(1) == O(n)，其中 n 是 self._table.

的大小

append是列表的原子操作，所以它被摊销O(1)，但是如果你达到这个操作，你已经完成了O(n)工作，所以它使方法O(n).

Answer 2

复杂度为O(n)。如果你看复杂性，你总是想象有非常大的数据要放入算法中。对于大数，O(n) 与 O(2n) 相同，后者不是大 O 的有效表示法，因为它不会造成 "big" 差异，而 O(n) 与 O(n^2) 相反，在计算复杂度上有很大的不同。由于您只循环一次列表 O(n)，因为您循环了 n 次，并且您的列表没有嵌套循环或任何昂贵的计算，所以总体复杂性保持 O(n) .

这个setitem方法的Big-O是什么？

What is Big-O of this setitem method?

python

big-o

dictionary

time-complexity