티스토리 뷰

알고리즘/기본개념

시간 복잡도

타올이 2023. 6. 12. 13:38
반응형

시간 복잡도

특정 알고리즘이 문제를 해결하는 데 필요한 컴퓨터 자원 중 하나인 '시간'을 측정하는 방법입니다. 알고리즘의 시간 복잡도는 입력의 크기에 대한 알고리즘의 실행 시간을 나타냅니다. 이를 표기하는 데에는 대게 Big O 표기법이 사용됩니다.

시간 복잡도 의미
O(1) 상수 시간(constant tiem)
O(logN) 로그 시간(log time)
O(N) 선형시간(linear time)
O(NlogN) 로그 선형 시간(log-linear time)
O(N^2) 이차 시간(quadratic time)
O(N^3) 삼차 시간(cubic time)
O(2^N) 지수 시간(exponential time)

O(1): 상수 시간(constant time)
상수 시간 복잡도를 가지는 알고리즘은 입력 크기에 관계없이 항상 일정한 시간이 걸립니다. 예를 들어, 배열에서 특정 인덱스의 값을 찾는 작업은 O(1)의 시간 복잡도를 가집니다.

O(logN): 로그 시간(log time)
로그 시간 복잡도를 가지는 알고리즘은 입력 크기를 계속해서 절반으로 줄여나갑니다. 이런 알고리즘의 대표적인 예는 이진 검색(Binary Search)입니다. 입력 크기가 두 배가 되어도, 한 단계만 더 거치면 되기 때문에 매우 효율적입니다.

O(N): 선형시간(linear time)
선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 비례해서 시간이 증가합니다. 예를 들어, 배열에서 최대값을 찾거나 모든 원소를 더하는 등의 작업은 O(N)의 시간 복잡도를 가집니다.

O(NlogN): 로그 선형 시간(log-linear time)
로그 선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 비례하되, 그 비율이 로그를 따릅니다. 병합 정렬(Merge Sort)이나 힙 정렬(Heap Sort) 등의 정렬 알고리즘이 O(NlogN)의 시간 복잡도를 가집니다.

O(N^2): 이차 시간(quadratic time)
이차 시간 복잡도를 가지는 알고리즘은 입력 크기의 제곱에 비례하여 시간이 증가합니다. 버블 정렬(Bubble Sort)이나 선택 정렬(Selection Sort) 등이 O(N^2)의 시간 복잡도를 가집니다.

O(N^3): 삼차 시간(cubic time)
삼차 시간 복잡도를 가지는 알고리즘은 입력 크기의 세제곱에 비례하여 시간이 증가합니다. 이런 시간 복잡도를 가지는 알고리즘은 비교적 드뭅니다. 3차원 데이터를 처리하거나, 행렬의 곱셈 등에서 볼 수 있습니다.

O(2^N): 지수 시간(exponential time)
지수 시간 복잡도를 가지는 알고리즘은 입력 크기에 대해 시간이 기하급수적으로 증가합니다. 피보나치 수열의 재귀적 계산 등이 이에 해당하며, 일반적으로 이러한 알고리즘은 매우 비효율적이라 할 수 있습니다.

반응형

'알고리즘 > 기본개념' 카테고리의 다른 글

javascript - 큐(queue)  (0) 2023.06.23
javascript - 스택(stack)  (0) 2023.06.22
집합 자료형 - Set  (0) 2023.06.15
배열 초기화  (0) 2023.06.14
Array.prototype.reduce()  (0) 2023.06.13
반응형
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/12   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31
링크
글 보관함