python - カウント関数の実行時の複雑さ

Question

def findTarget(myList, target):

    count = 0

    for item in myList:

         if (target == item):

              count = count + 1

    return count

これは 0(1) だと思いますが、これは 0(log)n であると言われましたか? 誰かが肯定または否定できますか?

Answer 1

ループにはN比較と加算未満がNあります。これにより、最大 2*N の操作が行われ、O(N) アルゴリズムが得られます。

リストの場合、これは組み込みメソッドであることに注意してください。

myList.count(item)

ループをCコードにプッシュします-それはまだO（N）ですが、そのバージョンはあなたのバージョンよりもはるかに高速に実行されるに違いありません:)。

Answer 2

ループはO(n)で、nは の長さですmyList。