[알고리즘 효율성] 시간 복잡도와 공간 복잡도 그리고 점근적 표기법 총정리

알고리즘 효율성 체크에서 쓰이는 시간 복잡도와 공간 복잡도, 그리고 Big-O 표기법에 대해 정리하고 넘어가고자 한다.

코테에서 어느정도 구현을 하다보면 시간 초과 혹은 메모리 초과를 겪는 경우가 많다.

그 때 어떤 곳을 최적화하면 좋을지 알고자 겸사겸사 정리하고 넘어가기로 한다.

알 때와 모를 때의 코드 구현은 정말 달라질 것이다.

 

📌 복잡도 & 점근적 표기법

 

복잡도, 그것이 무엇인가 🧐

컴퓨터 과학에서 알고리즘의 계산 복잡도(Computational Complexity) 혹은 복잡도(Complexity)라는 것은 알고리즘을 실행하는 데 필요한 자원의 양을 뜻한다.

이는 곳 알고리즘의 성능을 측정하는 데 사용되고, 복잡도가 작으면 작을 수록 해당 알고리즘이 효율적이라고 판단한다.

여러 복잡도가 있지만 대표적인 복잡도에는 시간 복잡도와 공간 복잡도가 있다. (분산에는 통신 복잡도도 쓰인다고 한다)

그럼 이 복잡도를 표기하기 위한 것이 필요하다.

 

✅ 점근적 표기법으로 복잡도를 나타낸다.

알고리즘의 성능을 설명하는 데 사용되는 수학적 표기법이다. 

점근적 표기법은 주어진 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다- 라고 위키가 말했다.

대체 이게 뭔말이야? 싶어서 더 찾아보았다.

 

💡 점근적 분석 이해를 위한 예제 ( multiply )

int[] multiply(int[] inputs, int multiplier) {
      int[] nums = new int[inputs.length];
      for (int i = 0 ; i < inputs.length ; i++) {
            nums[i] = inputs[i] * multiplier;
      }
      return nums;
}

실행 시간은 각 코드의 수행 단계별로 상수(고정적인 수)라고 가정한다.

위의 예제는 총 4단계의 수행 단계가 있는 것이다. nums 배열 생성, 반복문, 연산, 반환

 

1️⃣ 실행 시간을 나타내는 함수 T(N) 구하기

수행 단계	횟수
c1	1
c2	N+1
c3	N
c4	1

c1 : nums의 배열 생성은 1회이므로 1

c2: input의 길이 만큼 반복(N)하고, 루프 빠져나올때 한번 더 조건 검사(1)

c3: input의 길이 만큼 반복(N)

c4: 반환은 1회이므로 1

따라서 T(N)을 계산하는 수식을 정리하면,

T(N) = c1 + c2*(N+1) + c3*N + 1
        = (c2 + c3)*N + (c1 + c2 + 1)
        = a*N + b

이렇게 정리된다.

 

 

2️⃣ 반복 횟수가 무한대로 늘어난다면? N → ∞

N이 작을 땐 효율성 측정이 의미가 없으므로(어차피 빨리 끝나니까) 무한대라고 가정을 해보는 것이다.

이 때, 상대적으로 덜 중요한 정보는 빼버린다 → 최고 차항(N이 곱해진 것 중에 제일 수가 큰것)만 남기고 뺀다

최고 차항을 제외하면 무한대로 갈수록 그 영향력이 작아질 것이기 때문이다.

따라서 상수항인 b를 제거한다. 같은 이유로 최고차항의 계수인 a도 제거한다.

그럼 N만 남는다. 이걸 표기한 것이 𝚹(N) 빅 세타 N이다.

 

👉🏻 결론 : 이렇게 N이 무한으로 갈때 함수 T(N)이 어떤 형태의 함수로 근사하게 되는지를 분석하는 방식이 바로 점근적 분석이다.

 

💡 점근적 표기법 이해를 위한 예제 ( exits )

점근적 표기법에는 상한,하한,평균 뭐시기가 있는데 이게 어떻게 나오게 된건지 알아보도록 하겠다.

boolean exists(int[] inputs, int target) {
    for (int i = 0 ; i < inputs.length ; i++) {
        if (inputs[i] == target) {
            return true;
        }
    }
    return false;
}

이 예제는 어떤 한 배열에서 찾고자 하는 수가 있으면 true, 아니면 false를 반환한다.

앞의 예제와 다른 점은 target이 배열의 어느 위치에 있느냐에 따라 실행 시간이 차이가 난다는 것이다.

target이 앞에 있다면 일찍 끝날 테지만, 뒤에 있다면 늦게 끝날 것이다.

 

1️⃣ 최선과 최악의 상황으로 구분한다.

Best case와 Worst case로 나누어 실행 시간을 확인해본다.

Case	target 위치	횟수
Best	0번째 위치	1
Worst	마지막 위치 or 존재하지 않음	N

 

2️⃣ 시간 복잡도를 설명하는 두가지 방법

- 하한선(lower bound)을 기준으로 설명 : 함수 실행 시간은 아무리 빨라도 상수 시간(1) 이상이다. → 𝝮(1)

- 상한선(upper bound)을 기준으로 설명 : 함수 실행 시간은 아무리 오래 걸려도 N에 비례하는 정도 이하이다. → O(N)

👉🏻 결론 : 𝝮(1) , O(N) 둘다 맞는 설명이지만, 일반적으로는 상한선을 기준으로 얼마나 걸리는 지(제일 오래 걸릴 시간)를 궁금해하기 때문에 Big-O 표기법으로 나타내게 된 것이다.

그러나 Best, Worst 케이스 별로 각각 하한선, 상한선을 갖고 있으므로 각각 Big-Omega, Big-O를 표기할 수 있다.

Big-Theta는 tight bound를 의미하고, 이 상한선과 하한선이 같은 경우 이 값도 같은 값으로 표기할 수 있다. 

무지성으로 최악의 상황 = Big-O 표기값은 아니란 말이다. 

최선/최악 상황이 있고 각 상황별로 기준선(하한,상한)이 존재하니까 표기는 어느 상황이건 가능하다는 것이다.

 

 

 

 

시간 복잡도와 공간 복잡도 차이

- 시간 복잡도 : 알고리즘을 실행하는 데 걸리는 시간을 나타내는 척도

- 공간 복잡도 : 알고리즘을 실행하는 데 필요한 메모리 공간의 양을 나타내는 척도

 

📌 시간 복잡도

1. 시간 복잡도의 정의

컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도이다.

시간 복잡도의 이름에서 알 수 있듯이 시간의 복잡도와 로직의 수행 시간은 비례하므로 시간 복잡도의 수치가 작으면 작을 수록 효율적인 알고리즘임을 뜻한다.

 

2. 시간 복잡도 Case

종류	의미	특징
Every-Case Time Complexity ( 𝑇(𝑛) )	입력크기 n 이 입력됐을 때, 알고리즘이 연산을 수행하는 횟수	위의 multiply 예제에 해당. 입력 크기에만 종속되고, 어떤 입력값이 들어오더라도 일정. 𝑇(𝑛)으로 분석될 수 있으면  𝑊(𝑛) = 𝐴(𝑛) = 𝐵(𝑛) = 𝑇(𝑛)이 된다.
The Worst Case Time Complexity( 𝑊(𝑛) )	입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최대 횟수	입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최대인 경우
The Best Case Time Complexity ( 𝐵(𝑛) )	입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 최소 횟수	입력크기와 입력값 모두에 종속되며, 단위연산이 수행되는 횟수가 최소인 경우
The Average Case Time Complexity ( 𝐴(𝑛) )	입력크기 n 이 주어졌을 때, 알고리즘이 연산을 수행하는 평균 횟수	입력크기와 입력값 모두에 종속되며, 모든 입력에 대해서 단위연산이 수행되는 기대치

 

 

3. Big-O 표기법으로 보는 시간 복잡도

✅ 𝑂(1) < 𝑂(log n) < 𝑂(n) < 𝑂(nlog n) < 𝑂(n^2) < 𝑂(n^3) < 𝑂(2^n) < 𝑂(n!)

시간 복잡도의 순서이다.

💡 시간 복잡도 계산 예시

1. O(1) - 상수 시간(Contant time) : 입력 크기(n)에 상관없이 일정한 연산을 수행하는 시간복잡도 (배열의 인덱스 접근)

public void constantTime(int n){
	System.out.println("cool");
}

-> n의 크기가 무엇이든 간에 연산은 1번 수행됨

2. 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");
    }
}

-> i 증가폭이 2배 -> n의 로그만큼 횟수 증가

3. O(n) - 선형 시간(Linear time) : 입력크기(n)이 커지면 연산 횟수가 n에 비례해서 증가하는 시간복잡도 (선형 검색)

public void LinearTime(int n){
    for(int i = 0; i <= n; i++){
    	System.out.println("cool");
    }
}

-> n 만큼 증가

4. 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");
        }
    }
}

-> n*m 만큼 증가

5. O(2ⁿ) - 지수 시간(Expotential time) : 입력 크기(n)가 커지면 연산 횟수가 2ⁿ에 비례해서 증가하는 시간복잡도 (피보나치 수열(단순 재귀))

public int exponentialTime(int n){
    if(n <= 1){
    	return 1;
    }
    return exponentialTime(n-1) + exponentialTime(n-2);
}

 

📌 공간 복잡도

1. 공간 복잡도의 정의

알고리즘이 수행되는 데 필요한 메모리의 총량을 측정하는 척도이다.

총 메모리 공간 S(P)  = 고정 공간 요구 c + 가변 공간 요구 𝑆𝑝(𝑛)

• 고정 공간 : 코드 저장 공간, 단순 변수 및 상수, 알고리즘과 무관
• 가변 공간 : 해결하려는 문제의 동적으로 필요한 공간. 즉, 프로그램 성능에 영향을 미치는 공간
• 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 의해 좌우된다.

 

💡 공간복잡도 계산 예시 ( factorial )

int factorial(int n)
{
    if(n > 1) return n * factorial(n - 1);
    else return 1;
}

위의 코드는 n이 1이하가 될 때까지 스택에 모두 쌓이게 되므로 O(n)이라고 할 수 있다.

 

int factorial(int n)
{
    int i = 0;
    int fac = 1;
    for(i = 1; i <= n; i++)
    {
        fac = fac * i;
    }
    return fac;
}

반면에 위의 코드는 fac 변수에 i를 n까지 늘리면서 곱하고 업뎃하기 때문에 사실상 스택에는 n, i, fac만 있고, 이 때 공간 복잡도는 O(1)이 된다.

 

 

📌 Ref

https://easy-code-yo.tistory.com/13

https://velog.io/@dls4585/%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84Time-Complexity-%EC%A0%95%EB%A6%AC

https://dev-cool.tistory.com/19