计数功能的运行时复杂性

Question

def findTarget(myList, target):

    count = 0

    for item in myList:

         if (target == item):

              count = count + 1

    return count

有人告诉我这是0(log)n虽然我相信这是0(1)？有人可以确认还是否认？

Answer 1

你的循环已经N比较并且少于N加法 - 导致最多2*N个操作,这给你一个O(N)算法.

请注意,对于列表,这是一个内置方法:

myList.count(item)

这将循环推入C代码 - 它仍然是O(N),但我敢打赌,该版本将运行比你的版本更快:).