1. 복잡도(Complexity)
복잡도란 알고리즘의 성능을 나타내는 지표이다.
복잡도는 가독성(Readability)와 다른 의미로 쓰인다. 즉, 코드가 얼마나 복잡하고 알아보기 어려운지를 의미하는 것이 아니라 불특정한 함수의 성능적인 측면에서의 복잡도를 의미한다.
1. 시간 복잡도(Time Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
2. 공간 복잡도(Space Complexity) : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
이때, 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮은 알고리즘이 좋은 알고리즘이다.
2. 시간 복잡도(Time Complexity)
빅-오 (Big-O) 표기법
시간 복잡도란 특정 알고리즘이 문제상황을 해결하는데 걸리는 시간을 의미한다.
같은 결과를 가져오는 코드라면 시간 복잡도가 작을수록 더 효율적인 알고리즘인 것이다.
시간 복잡도는 여러가지 개념이 있지만 그중 'worst case' 를 기준으로 표기하는 빅-오(Big-O) 표기법을 사용한다.
즉, 아무리 오래걸려도 이것보단 오래걸리지 않는시간을 기준으로 알고리즘의 성능을 표기하는 것이다.
시간복잡도 표기
- 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ⁿ에 비례하여 연산횟수가 증가한다.
시간 복잡도를 줄이는 방법
1. 반복문의 숫자를 줄이자
2. 적절한 자료구조의 사용
3. 적절한 알고리즘의 이용
3. 공간 복잡도(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) 이다.