알고리즘은 뭘까?
- 알고리즘은 어떤 일을 하기 위한 명령의 집합이다. 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미한다.
- 알고리즘은 각기 다른 모양과 형태를 가지고 있기 때문에 타임 복잡도를 설명하는데 자주 사용된다.
- 시간 복잡도를 분석하는 것은 알고리즘이 문제를 해결하는 데에 어느 정도의 시간이 걸리는 지를 분석하는 것과 같다.
그리고 이는 Big-O 표기를 사용해 정의할 수 있다.
빅오 표기법
빅오 표기법(Big O notation)
은 알고리즘이 얼마나 빠른지 표시하는 특별한 방법이다.
- 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타낸다.
- 최악의 실행 시간을 나타내는 빅오 표기법 :
O(n)
-> 단순 탐색의 실행 시간
많이 사용하는 빅오 실행 시간 예시
Regular Big-O
2 O(1) --> It's just a constant number
2n + 10 O(n) --> n has the largest effect
5n^2 O(n^2) --> n^2 has the largest effect
시간 복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다.
- O(log n), 로그 시간 : 이진 탐색
- O(n), 선형 시간 : 단순 탐색
- O(n * log n) :
퀵정렬
과 같이 빠른 정렬 알고리즘
- O(n²) :
선택 정렬
과 같이 느린 정렬 알고리즘
- O(n!) : 정말 느린 알고리즘
정리
- 이진 탐색은 단순 탐색보다 아주 빠르다.
O(log n)
은 O(n)
보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라진다.
- 알고리즘의 속도는 시간으로 측정하지 않고, 연산 횟수가 어떻게 증가하는 지로 측정한다.
- 알고리즘의 시간은 빅오 표기법으로 나타내며, 어떻게 증가하는가로 측정한다.