Algorithms

시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는데 필요한 시간이 얼마나 걸리는지를 나타내는 척도이다. 이는 일반적으로 알고리즘 입력의 크기에 대해 실행 시간이 어떻게 증가하는지를 나타내는 함수로 표현된다.

위는 합병 정렬(Merge sort)의 시간 복잡도를 나타낸다. 위와 같은 재귀식 형태로는 알고리즘의 시간 복잡도를 정확히 알 수 없다. 점화식 풀이를 위해, 아래의 3가지 방법을 사용할 수 있다.

정렬 알고리즘은 데이터 요소들을 특정 순서대로 정렬하는 알고리즘이다. 일반적으로 리스트나 배열 같은 데이터 구조에 저장된 요소들을 오름차순이나 내림차순 같은 순서로 재배열하는 데 사용된다.

해시 함수는 데이터를 고정된 길이의 해시값으로 변환하는 함수이다. 해시 함수를 이용한 저장, 삭제, 검색은 모두 $O(1)$의 시간 복잡도를 가진다.