행복을 담는 블로그
[자료구조] 알고리즘, 시간 복잡도 / 공간 복잡도 본문
시간 복잡도 (Time Complexity)?
: 프로그램을 실행하는데 실제로 시간이 얼마나 걸리느냐?를 나타내는 척도를 의미한다.
시간을 측정하는 2가지 방법
- 실제 소요되는 시간을 측정 : 컴퓨터의 프로그램이 시작하는 시간 ~ 끝나는 시간까지 차이 비교
❗️문제점 : 컴퓨터 CPU의 성능에 따라 실제 실행되는 시간이 달라지기 때문에, 같은 코드로 짠 프로그램이라도 실행 시간이 달라질 수 있다.
- 실행되는 명령문의 개수를 계산 : 프로그램 내에서 실행되는 명령문의 수로 시간이 걸리는 정도를 알아본다.
❗️문제점 : 프로그램이 복잡해질수록 명령어가 많아지므로, 현실적으로 확인하기 어렵다.
💡 시간 복잡도란?
"입력 크기에 따라 어떠한 알고리즘이 실행되는 데 걸리는 시간"
주로 로직의 반복 횟수를 중점으로 처리되며, 보통은 "빅오 표기법"으로 나타낸다.
<시간 복잡도 유형>
- Big-Ω(빅-오메가) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
- Big-θ(빅-세타) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
- Big-O(빅-오) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
빅-오(O) 표기법(Big-Oh Notation)
: 시간 복잡도 함수 중에서 가장 큰 영향력을 주는 n에 대한 항만 표시하는 표기법
입력의 크기가 커질수록 연산량이 가장 많이 커지는 항만 신경 쓰면 된다는 이론.
ex)
O(3n + 2) = O(3n) = O(n)
: 가장 영향을 많이 미치는 최고차항만 남기고, 상수 인자 제거.
O(2n^2 + 10n + 100) = O(n^2)🤔 그렇다면 시간 복잡도는 왜 필요할까?
: 비효율적인 코드를 효율적인 코드로 쓰이는 척도로 사용. = 최적화를 위해서
데이터를 저장할 수 있는 공간은 메모리와 저장매체의 발전으로 어느정도 커버 가능하나, 시간은 돈으로 살 수 없기에 시간 단축은 필수!
시간 복잡도의 속도 비교
: 입력 데이터의 n의 크기가 커질수록, 연산 수(= 실행시간)가 어떻게 바뀌는지 비교
x축에 접할수록 연산 시간이 적다는 얘기이므로, 좋은 알고리즘이다.
O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(2^n) > O(n!)순으로 효율적인 알고리즘이다.
O(1)
: 상수 시간 (Constant Time) - 입력 크기와 상관없이 일정한 시간이 걸린다.
O(log n)
: 로그 시간 (Logarithmic Time) - 이진 탐색처럼 입력 크기가 두 배로 증가할 때마다 실행 시간이 일정한 단위로 증가한다.O(n)
: 선형 시간 (Linear Time) - 입력 크기에 비례해서 실행 시간이 증가. 예를 들어, 단순 검색에서 리스트의 모든 요소를 확인해야 할 때 발생한다.
O(n log n)
: 선형 로그 시간 (Linearithmic Time) - 흔히 사용되는 정렬 알고리즘 중 몇몇이 이 시간 복잡도를 가진다. (예: 병합 정렬).
O(n^2), O(n^3), ...
: 다항 시간 (Polynomial Time) - 중첩 루프와 같은 구조를 사용할 때 발생하는 시간 복잡도.
O(2^n)
: 지수 시간 (Exponential Time) - 알고리즘의 실행 시간이 입력 크기에 따라 지수적으로 증가한다.
O(n!)
: 팩토리얼 시간 (Factorial Time) - 순열 문제 같은 경우에 발생하는 시간 복잡도.
자료 구조의 평균/최악 시간 복잡도
참고 https://blog.chulgil.me/algorithm/
공간 복잡도
: 프로그램을 실행시켰을 때, 필요로 하는 자원 공간의 양
/* C++ */
int a[1004];→ a 배열은 1004 * 4 바이트의 크기를 가진다. = 공간을 가진다.