计数函数的时间复杂度

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

这个循环的复杂度是 O(n)，其中 n 是 myList 的长度。

Answer 2

你的循环有 N 次比较和少于 N 次的加法运算，这样总共最多会有 2*N 次操作，所以这个算法的复杂度是 O(N)。

需要注意的是，对于列表来说，这里有一个内置的方法：

myList.count(item)

这个方法会把循环转成 C 代码——虽然它的复杂度还是 O(N)，但我敢打赌这个版本的运行速度会比你的版本快很多 :).