python - 如何获得代码的大 O 时间复杂度？

Question

我对大 O 表示法有很好的理解，但我对这个问题很困惑：

给定一个具有 N 个元素的排序列表，并且正在搜索的键在列表中重复 R 次，就 O 表示法而言 my_search() 的复杂性是多少？

def my_search( data, key ):
 found = False
 low = 0
 count = 0
 high=len(data)-1
 while ( not found and low<=high):
     guess = (high+low)//2
     print('guess: ', guess)
     if ( key == data[guess] ):
         found = True
         count = 1
         k = guess - 1
         while k>=0 and data [k] == key:
             count += 1
             k -= 1
         k = guess + 1
         while k < len(data) and data [k] == key:
             count += 1
             k += 1
     else:
         if (key < data[guess]):
             high=guess-1
         else:
             low = guess+1
 print('count:', count)
 return count

此函数传递的参数是一个列表和一个键，该函数计算该键在列表中出现的次数，例如my_search([1,1,2,2,3,3,3,3,3,3,6,7], 1). 答案的关键是这段代码的时间复杂度是 ，他们是怎么得出这个答案的？

标签： pythontime-complexitybig-o

Answer 1

在有序列表中搜索是 O(log(N)) （二分搜索）。找到要查找的元素后，您需要根据您搜索的项目检查（至少）R 元素。所以总共 O(log(N)) + R。