-
알고리즘의 시간을 표현하기(시간복잡도 / Time Complexity)컴퓨터 기초/알고리즘&자료구조 2020. 7. 21. 05:25
알고리즘은 효율적으로 짤수록 시간과 자원이 굉장히 줄어드는 효과를 볼 수 있다.
그리고 이러한 알고리즘이 수행하는데 걸리는 시간의 상한선 하한선을 시간복잡도로 표현할 수 있다.
시간복잡도가 낮을수록 해당 알고리즘이 더욱 효율적이라고 볼 수 있다.
시간복잡도에서 알고리즘의 실행시간 상한선은 Big-O 표기법을 사용해 나타낸다.
O(1)
상수의 형태
O(log n)
로그 형태
이진 탐색
O(n)
선형 형태
선형 탐색
O(n long n)
선형로그 형태
퀵정렬, 병합정렬(합병), 힙정렬
O(n^c)
다차 형태
선택정렬, 버블정렬, 삽입정렬
해당 표에서는 O(1)가 가장 빠르고 O(n^c)가 가장 오래 걸린다.
이러한 시간 복잡도는 대략적인 큰 숫자를 비교하는 것을 기본으로 한다.
이유는 작은 수를 하나하나 헤아리는 것은 전체 데이터의 처리 시간에 큰 영향을 주지 않기 때문이다.
Big-O의 반대 개념도 있다.
알고리즘 실행시간의 하한선은 Big-Omega(Ω)를 사용해 나타낸다.
Big-Omega는 알고리즘 배열 상태가 최적일 때 최소한의 실행에 걸리는 최적의 시간을 나타내는 것과 같다.
Ω(1)
선형탐색, 이진탐색(한 번에 찾는 경우) Ω(log n)
Ω(n)
배열 안의 모든 숫자 세기 Ω(n log n)
Ω(n^2)
해당 표에서는 Ω(1)가 가장 빠르고 Ω(n^2)가 가장 오래 걸린다.
다만 빅 오메가는 알고리즘 설계시 빅오에 비해 중요성이 덜할 수 밖에 없는 그건 바로 항상 최적의 조건으로 데이터들이 정렬되어 있는 것이 아니기 때문이다.
그리고 시간의 하한선과 상한선이 같은 경우가 있는데 이 경우엔 Big-Theta(θ)라고 써준다.
'컴퓨터 기초 > 알고리즘&자료구조' 카테고리의 다른 글
최대값, 최소값, 중간값 구하기 - 자료구조와 함께 배우는 알고리즘 입문(자바) (0) 2021.04.12 알고리즘이란? - 자료구조와 함께 배우는 알고리즘 입문(자바) (0) 2021.04.12 알고리즘 - merge sort (합병정렬) (0) 2020.07.21 알고리즘 - selection sort (선택정렬) (0) 2020.06.26 알고리즘 - bubble sort(버블 정렬) (0) 2020.06.26