python - 计数函数的运行时复杂度

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)，但我敢打赌那个版本会比你的版本运行得快很多:)。

Answer 2

循环是O(n)，其中n是 的长度myList。