[アルゴリズム]白駿1920(Python)

7421 ワード
白駿 パイ アルゴリズム#アルゴリズム# テキストリンク
cotteのためにアルゴリズムを練習すると、ますます時間の複雑さを考えてしまいます.答えは正しいのにタイムアウトが表示されるからです.1920年のPython時間の複雑さに関する注意点を解く?あるいは小さなシールに簡単に記入します.


『シルバー4』ですが正解率は低いです
原因は처음 접근법을 그냥 완전탐색처럼 하는 경우と이분탐색을 했지만 하는 과정에서 시간복잡도가 늘어나는 경우です.
まず最初の理由を見て
私も最初は.

if i in list_A:
	print(1)
同じ方法で解き、タイムアウトしました.
この問題の要旨はこの人を探求することだからだ.
でもこの方法にも解法があります
数字の並びはリストではなくsetです.
setはindexを検索するのにO(1)の時間が必要だと言います.このような問題は,重複する場合も順序もないのでsetで解決する方法があるはずである.
二つ目の理由を見て
この問題はこの探索で解決したもので,それもこの探索で解決しなければならない.
import sys
A=int(sys.stdin.readline())
B=list(sorted(map(int,sys.stdin.readline().split())))
C=int(sys.stdin.readline())
D=list(map(int,sys.stdin.readline().split()))

def binary(B,value):
    n=len(B)
    if B[-1]<value or B[0]>value:
        return 0
    if n == 1:   #리스트가 1개일 때
        if B[0] == value:
            return 1
        else:
            return 0
    if B[n//2] == value: #리스트 가운데 값과 비교
        return 1
    if B[n//2] > value: # 큰지 작은지에 따라 재귀
        return binary(B[:(n//2)],value)
    if B[n//2] < value:
        return binary(B[(n//2)+1:],value)


for i in D:
    print(binary(B,i))
しかし不思議なことにいつもタイムアウトが発生します
元々Pythonでlistスライスを行うとO(n)の時間的複雑さがある.そのためbinaryを1回実行するたびに時間の複雑さが上昇します.
どうすればいいの?
答えは簡単で、スライスする必要はありません.起点と終点を確定して範囲を指定すればいいだけです.
FormatMessageエラーメッセージ
pvfs 2コードpvfs 2-ls.c