시간 복잡도(Time Complexity)
시간 복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.
같은 결과를 갖는 프로그래밍 소스도 작성 방법에 따라 걸리는 시간이 달라지며,
같은 결과를 갖는 소스라면 시간이 적게 걸리는 것이 좋은 소스이기 때문입니다.
빅-오 (Big-0) 표기법
시간 복잡도는 여러가지 개념이 있지만 그중 'worst case'를 기준으로 표기하는 빅-오(Big-O) 표기법을 사용한다.
예를 들어, 동전을 튕겨 뒷면이 나올 확률을 이야기 할 때 운이 좋으면 1번만에 뒷면이 나오지만 운이 안 좋다면 n번 만큼 동전을 튕겨야 하는 경우가 발생합니다.
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부릅니다.
- 여기서 n이란 입력되는 데이터를 의미한다.
O(1) - 상수 시간(Contant time)
입력 크기(n)에 상관없이 일정한 연산을 수행하는 시간복잡도 이다.
public void constantTime(int n){
System.out.println("cool");
}O(log₂ n) - 로그 시간(Logarithmic time)
입력 크기(n)이 커지면 연산 횟수가 log₂ n에 비례해서 증가하는 시간 복잡도이다.
public void LogarithmicTime(int n){
for(int i = 0; i <= n; i*2){
System.out.println("cool");
}
}O(n) - 선형 시간(Linear time)
입력 크기(n)가 커지면 연산 횟수가 n에 비례해서 증가하는 시간복잡도이다.
public void LinearTime(int n){
for(int i = 0; i <= n; i++){
System.out.println("cool");
}
}O(n²) - 2차 시간(Quadratic time)
입력 크기(n)가 커지면 연산 횟수가 n²에 비례해서 증가하는 시간 복잡도이다.
public void QuadraTime(int n){
for(int i = 0; i <= n; i++){
for(int j = 0; j <= n; j++){
System.out.println("cool");
}
}
}O(2ⁿ) - 지수 시간(Expotential time)
입력 크기(n)가 커지면 연산 횟수가 2ⁿ에 비례해서 증가하는 시간 복잡도이다.
public int exponentialTime(int n){
if(n <= 1){
return 1;
}
return exponentialTime(n-1) + exponentialTime(n-2);
}이 알고리즘은 피보나치 수를 구하는 알고리즘으로 재귀함수를 이용하여 한번 함수를 호출할 때마다 두번씩 재귀로 함수를 호출하여 2ⁿ에 비례하여 연산 횟수가 증가한다.
공간 복잡도(Space Complexity)
공간 복잡도란 작성한 프로그램이 얼마나 많은 메모리를 차지하는지 분석하는 방법이다.
하지만 최근 컴퓨터 성능의 비약적인 발전으로 중요성이 예전보다 많이 떨어지고 있지만, 데이터를 많이 다루는 빅데이터 분야에서는 여전히 중요한 지표로 다뤄진다
public int factorial(int n){
int i = 0;
int result = 1;
for(i = 0; i < n; i++){
result *= i;
}
return result;
}다음은 팩토리얼 결과를 반환하는 메소드로 지역변수로 i, result 를 선언하였다.
입력값인 n에 대해서 for문이 n번 반복하지만 for문 안에 지역변수 이므로 공간 복잡도에 아무런 영향을 끼치지 않는다. 따라서, 공간 복잡도는 O(1)이다.
public int factorial(int n){
if(n > 1) {
return n * factorial(n-1);
}else{
return n;
}
}위와 같이 재귀함수를 호출하는 경우는 입력값인 n에 따라 재귀적으로 메서드가 호출되므로 스택에는 n부터 1까지 모두 쌓이며 위 코드의 공간 복잡도는 O(n) 이다.
결론
💡 정리
시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
