시간복잡도(Time Complexity)
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다.
예를 들어 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 5n^3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)이라고 할 수 있다.
알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 최악의 시간 복잡도의 알고리즘 시간을 T(n)이라고 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 최대의 시간으로 정의할 수 있다. 따라서 일반적으로 Big-O는 대부분 최악의 경우를 표현한다.
시간 복잡도는 함수 T(n)의 특성에 의해 분류할 수 있다. 예를 들면, T(n)=O(n)인 알고리즘은 선형 시간 알고리즘이라고 부르며, 몇몇 M ≥ n >1에 대해 T(n)=O(Mn)이고 Mn=O(T(n)) 인 알고리즘은 지수 시간 알고리즘이라고 한다.
출처 : https://ko.wikipedia.org/wiki/시간_복잡도
선형 시간 복잡도에서 지수 시간복잡도로 갈수록 프로그램의 수행시간이 길어진다.
O(1) - Constant
입력되는 데이터양과 상관없이 일정한 실행 시간을 가진다.
알고리즘이 문제를 해결하는데 오직 한 단계만 거친다.
예시)
- 배열의 index로 접근할 때
numbers = [ 100, 20, 30, 15 ]
print(numbers[3])
- Stack 이나 Queue 자료구조에서의 삽입 혹은 삭제
O(logN) - Logarithmic
데이터의 양이 많아져도, 시간이 조금씩 증가한다.
문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.
- Binary Search
O(N) - Linear
데이터양에 따라 시간이 정비례한다.
- Linked List에서의 데이터 삽입(중간 삽입이 가능한 경우)
- 선형 탐색, for 문을 통한탐색이 해당한다.
userInput = input("숫자 입력")
for i in range(int(userInput))
print("hi")
O(NlogN) - Linearithmic
데이터양이 N배 많아 지면, 실행 시간은 N배 보다 조금 더 많아 진다.
커다란 문제를 독립적인 작은 문제로 쪼개어 각각에 대해 독립적으로 해결하고 다시 그것들을 하나로 모으는 경우에 해당한다.
- QuickSort
https://www.geeksforgeeks.org/quick-sort/ - MergeSort
https://www.geeksforgeeks.org/merge-sort/
O(n^2) Quadratic
데이터양에 따라 걸리는 시간은 제곱에 비례한다. (효율이 좋지 않다.)
- 2중 for 문, 삽입정렬(insertion sort)
https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/
공간복잡도(Space Complexity)
-프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양, 즉 메모리 공간의 총량
총 공간 요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있으며
S(P) = c + Sp(n) 으로 표기한다.
여기서 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구(코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)를 말한다.
가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간 즉, 동적으로 필요한 공간을 말한다.
아래의 코드를 통해 공간 복잡도의 예시를 살펴보면
def factorial(n):
if n > 1 : return n * factorial(n - 1)
else : return 1
위 코드에서 n이 1이 될 때까지 함수가 재귀적으로 호출되므로 스택에는 n부터 1까지 모두 쌓이게 된다. 즉 공간 복잡도는 O(n)O(n) 이 된다.
똑같은 함수를 아래와 같이 구현한 경우를 살펴보자.
def factorial(n):
i = 0
fac = 1
for i in range(1, n+1):
fac = fac * i;
return fac;
n의 값에 상관없이 스택에는 n과 i 그리고 fac 변수만 저장되며 여기서의 공간 복잡도는 O(1)O(1) 입니다
시간 복잡도 vs 공간 복잡도
좋은 알고리즘이란 시간 복잡도와 공간 복잡도가 모두 낮은 것이겠지만, 일반적으로 시간 복잡도와 공간 복잡도는 반비례적인 경향이 있기 때문에 알고리즘의 척도는 시간 복잡도를 위주로 판단한다.
출처: https://madplay.github.io/post/time-complexity-space-complexity