알고리즘 (2) 썸네일형 리스트형 해시 테이블 원리 및 구현 (With Python) 1. 정의 키를 값에 매핑할 수 있는 구조인 연관 배열 추상 자료형을 구현한 자료구조이다. 가장 큰 특징은 시간 복잡도가 O(1)이라는 점이다. 덕분에 데이터 양에 관계없이 빠른 성능을 기대할 수 있다. 해시 테이블의 핵심은 해시 함수이다. 해시 함수는 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라 한다. 성능 좋은 해시 함수들의 특징은 아래와 같다. 해시 함수 값 충돌 최소화 쉽고 빠른 연산 해시 테이블 전체에 해시 값이 균일하게 분포 사용할 키의 모든 정보를 이용해 해싱 해시 테이블 사용 효율이 높을 것 2. 충돌 해시 테이블에 충돌은 얼마나 많이 발생할까? 생각보다 쉽게 일어난다. 예시로 생일 문제를 들 수 있다.. 알고리즘 복잡도 1. 복잡도 시간 복잡도: 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도: 알고리즘을 위해 필요한 메모리의 양 2. 빅오 시간 복잡도를 표현할 때 빅오(BIG-O) 표기법 사용. 빅오 표기법은 가장 빠르게 증가하는 항(큰 차수를 가진 항)만 고려하는 표기법이다. 아래는 빅오 표기법 종류에 대해 설명하는 사진이다. O(1) = 상수 연산. 연산 한 번이 수행된다. ex) a=5 b=7 print(a+b) O(n^2) = 보통 2중 반복문(for) 이용. 그러나 모든 2중 반복문 시간 복잡도가 O(n^2)이 아니다. 만약 코드가 내부적으로 다른 함수를 호출하면 내부 함수의 시간 복잡도까지 고려해야 한다. 3. 알고리즘 설계 Tip 컴퓨터 연산 횟수가 5억 넘을 경우:C언어를 기준으로 1초 이상 시간 소요... 이전 1 다음
