代码片段的大 O 时间复杂度 Python

Question

我是 Python 的新手，所以我仍然不太擅长确定某些程序的 Big O 时间复杂度。我想寻求一些帮助。这里有一些代码片段，我很难知道 Big O 是什么，以及我认为 Big O 是什么：

代码 1：O(n)

def foo(n):
   i = 0
   k = 0
   for i in range(0,len(n)):
      for j in range(0,k):
         n[i] = k + 1
         k = 0
   k += 1

代码2：我其实不知道这里

def bar(x,i,j,y):
   if j >= i:
      foo = (i+j) // 2
      if x[foo] == y:
         return foo
      elif x[foo] > y:
         return bar(x,i,foo-1,y)
      else:
         return bar(x,foo+1,j,y)
   else:
      return -1

代码 3：O(m)

def count(a,b):
   # Let len(a) = m
   # Let len(b) = n
   count = 0
   for char in a:
      if char in b:
         count += 1
   return count

如果您愿意，请提供一些关于查找与这些代码片段相似的程序的 Big O 的提示。任何帮助将不胜感激。谢谢！

Answer 1

代码 1 令 N 为 n 的长度。此代码将是 O(N) 但它不会执行任何操作，因为内部 for 循环会迭代 range(0,0).

代码2 设 N 为 x 的长度。假设 i 和 j 在列表 x 具有索引的范围内。最坏的情况是 y 不在 x 中并且 j - i 尽可能大。这大约需要 O(j-i)，不超过 O(N)。因此，平均而言，此过程需要 O(N) 或更少。

代码 3 如果 char in b 取 O(1) 可能是这种情况，但我不这么认为。可能需要 O(n) 所以算法是 O(mn)

对于简单的算法，只需手动计算循环即可。如果算法中有递归，使用一种方程式并计算它应该迭代多少次可能会有所帮助。这是相关问题：Determining complexity for recursive functions

代码片段的大 O 时间复杂度 Python

Big O Time Complexity of Code Snippets Python

python

big-o