2

数値とその double が配列に存在するかどうかを確認する必要があります。このコードを使用setして解決します。ただし、時間の複雑さが よりも優れているかどうかはわかりませんO(N^2)。私は以下のように使用しfor loopますif 2*item in s。アイテムが配列内にあるかどうかを知るためではないか、別の を使用しO(N)ます。O(N^2)合計ってどういうこと？最適な場合、を使用せずに C でコードを実装するにはどうすればよいnested loopですか?
どうもありがとう！

  def checkIfExist(arr]) -> bool:
    s = set(array)
    for item in s:
        if 2 * item in s and item != 0:
            return True
    if arr.count(0) >= 2:
        return True
    return False
4

1 に答える 1

1

Python のセットの 'in' 演算子の時間計算量は、平均 O(1) であり、最悪の場合 O(N) のみです。これは、Python のセットが HashTable を内部的に使用するためです。

したがって、関数の平均的な時間の複雑さは O(N) である必要があり、最悪の場合のみ O(N^2) になります。ここで、N は配列の長さです。

詳細はこちらhttps://wiki.python.org/moin/TimeComplexity

于 2021-04-24T08:00:07.933 に答える