h0ngjun7   3년 전

사전의 단어 개수가 N(10^4 이하), 사전에 특정 단어가 존재하는지 질문의 개수가 M(10^4 이하), 모든 단어의 길이는 최대 500(=L)

1. trie 만들어서 풀기. O((N+M)L) → python 3 : 5.0초

2. 각 쿼리 단어 y에 대해 x in 사전 식으로 비교해서 풀기. O(NML) → python 3 : 2.5초


이렇게 수행시간이 측정되니 의문이 생깁니다.

파이썬에서 두 문자열이 같은지 비교하는 연산은 O(길이)라고 알고 있는데, 그럼 'x in 사전'이 데이터가 약해서 빨리 수행된 것인지 궁금하네요.

trie를 만드는 데 수행시간이 조금 걸리는 것은 충분히 이해가 되는데, 2번이 생각보다 너무 빨리 수행되서 신기합니다.

도움주시면 감사하겠습니다.

jh05013   3년 전

dict는 해싱을 사용하기 때문에 평균 O(1)의 lookup 시간을 가집니다.

h0ngjun7   3년 전

우와....  감사합니다 찾아보니 worst는 O(N)이지만 그럴 확률이 매~우 낮다고 하는군요.

https://stackoverflow.com/ques...

댓글을 작성하려면 로그인해야 합니다.