ycj123z   2년 전

안녕하세요.

처리시간에 대해 질문드립니다.

우선 저는 이분탐색으로 문제를 풀어 2904ms가 걸려 문제를 해결했습니다.

그런데 다른사람들의 풀이를 보아하니 set dict를 해서 시간초과를 해결하셨더군요

그냥 list로 배열안에 있는 원소를 찾는 것과 dict,set으로 형변환 후 원소를 찾는 것과 왜 시간차이가 나고 후자가 시간효율이 좋나요??

아래는 제 코드입니다.

kong_22   2년 전

시간 복잡도의 관점에서 보면, 어떤 원소가 list에 있는지 판별하는 것은 O(n)이고,

set이나 dictionary는 주어진 key를 해쉬를 이용하여 바로 찾기 때문에 O(1) 입니다.

'파이썬 시간복잡도' 등으로 검색해보시면 각 자료형의 시간복잡도가 정리된 표 등이 있으니 한번 확인해보세요!

bupjae   2년 전

특정한 데이터 x 가 n개의 데이터를 가지고 있는 자료구조 a 안에 들어있는지 알아보는 시간복잡도가

배열(list)은 O(n), 이분 탐색은 O(log n), 집합(set)은 O(1) 입니다.

이를 m 번 반복해야 하므로 시간복잡도는 각각 O(mn), O(m log n), O(m) 이 됩니다.

 

또한, 이분 탐색을 하기 위해서는 정렬된 배열이 필요하므로 O(n log n) 의 전처리 과정이 필요하며.

그 외 자료구조는 데이터 n개가 들어오는 대로 넣기만 하면 되므로 O(n) 의 전처리 과정을 거치는 셈입니다.

   

결론적으로 전체 프로그램의 시간복잡도는

배열은 O(mn), 이분 탐색은 O( (m+n) log n), 집합은 O(m+n) 이 됩니다.

n 과 m 에 다양한 수를 넣어보면 필요한 연산의 횟수를 대략적으로 알 수 있습니다.

ycj123z   2년 전

감사합니다~~!!

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