[F-Lab 모각코 챌린지 11일차] 시간복잡도, 공간복잡도

TIL

1. 시간복잡도
   • Big-O 표기법
2. 공간복잡도

 

---

 

시간복잡도

시간복잡도란 입력크기에 대해 어떤 알고리즘이 실행되는데 걸리는 시간이다. 주요 로직의 반복횟수를 중점으로 측정된다. 근데 그냥 실제 시간을 측정하면 안 될까? 컴퓨터 사양마다, 같은 컴퓨터라도 CPU나 RAM 상태에 따라 시간이 다르게 측정된다.

 

즉, 실제 시간을 측정하는 것은 여러가지 변수에 영향을 받는다.

 

그래서 시간복잡도를 설명할 때, 실제 시간이 아니라 주어진 입력크기를 기반으로 주요 로직이 몇 번 반복되었는가를 중점으로 보는 것이다.

 

for(int i = 0; i < 10; i++){ // 10번 반복됨
    for(int j =0; j < n; j++){ // n번 반복됨
        for(int k = 0; k < n; k++){ // n번 반복됨
            if(true) cout << k << '\n';
        }
    }
}

for(int i = 0; i < n; i++){ // n번 반복됨
    if(true) cout << i << '\n';
}

if(true) cout << k << '\\n' 로직이 얼만큼 반복될까? 삼중 반복 for문의 2, 3번째 for문이 n번 돌고 1번째 for문이 10번 반복된다. 그리고 하단에 있는 for문이 n번 반복된다.

즉, 주요로직이 10 X n^2 + 10 반복된다. 이렇게 표기하는 것이 시간복잡도이다.

 

 

 

Big-O 표기법

복잡도에 가장 영향을 많이 끼치는 항의 상수인자와 나머지 항을 없애서 복잡도를 표시하는 표기법이다.

여기서 가장 많은 영향을 끼치는 항은 무엇일까? 입력크기가 커지면 커질수록 증가속도가 빠르게 증가하는 항을 말한다.

예를 들어, 10n^2 + n이라는 항이 있을 때, n이 1, 3, 9, 12로 증가한다. n^2은 1, 9, 81, 144로 증가한다. n^2이 훨씬 더 급격하게 증가하는 것을 볼 수 있다. 이 때 10n^2이 가장 영향을 많이 끼치는 항이라고 볼 수 있다.

n항과 상수(여기선 10)가 끼치는 영향은 n^2항에 비해 미미하기 때문에 다 제거한다.

또, 빅오표기법은 최악의 경우를 대비하여 계산하는 방식이다. (최선의 경우를 대비하여 계산하는 방식은 빅-오메가, 평균의 경우를 대비하여 계산하는 방식은 빅-세타 표기법이다.)

 

빅오표기법 차트

n! > 2^n > n^2 > nlogn > n > logn > 1

 

 

 

O(1) (Constant)

입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸린다. 입력 데이터가 얼마가 증가하든 성능에 영향을 미치지 않는다. 배열 인덱스를 사용해 값에 접근하는 것을 예로 들 수 있다.

int arr[] = {1, 2, 3, 4, 5};

int value = arr[2]; // 3

 

 

 

O(logN) (Logarithmic)

입력 데이터의 크기가 커질수록 처리 시간이 로그(logN)만큼 짧아진다.
이진탐색이 대표적이고 재귀가 순기능으로 이루어지는 경우에도 해당된다.

for (var i = 1; i < n; i = i * 2) {
    System.out.println(i);
}

// n = 32 ====> 5번 반복
// n = 64 ====> 6번 반복
// n = 128 ===> 7번 반복
// ✔입력값 n의 크기에 따라 주요로직이 lonN만큼 반복되고있다.

 

 

 

O(n) (Linear)

입력 데이터의 크기에 정비례해 처리 시간이 증가한다. 예를 들어, 데이터가 10배가 되면 처리 시간도 10배가 된다.

String fruits[] = {"orange", "apple", "banana", "lemon", "melon"}; // 5steps

for (int i = 0; i < fruits.length; i++) {
    System.out.println(fruits[i]);
}

 

 

 

O(NlogN) (Linear-Logarithmic)

데이터가 많아질수록 처리시간이 로그(log) 배만큼 더 늘어난다. 예를 들어, 데이터가 10배가 되면, 처리 시간은 약 20배가 된다. 정렬 알고리즘 중 병합, 퀵 정렬이 대표적이다.

 

 

 

O(n^2) (quadratic)

알고리즘을 실행하는데 걸리는 시간이 입력 크기의 제곱에 비례하는 경우, 이 알고리즘은 2차 시간복잡도를 갖는다.
중첩된 for문과 같이 중첩 반복과 관련된 알고리즘에서 2차 시간복잡도가 발생한다.

• 단, m이 n보다 작을 때는 O(nm)으로 표시하는 것이 바람직하다.

• n^3과 n^5도 모두 O(n^2)이라고 표기한다. n이 커질수록 지수가 주는 영향력이 퇴색되기 때문이다.

int n = 5; // 입력크기
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // do something for 1 second
    }
}

 

 

 

O(2ⁿ) (Exponential)

데이터량이 많아질수록 처리시간이 기하급수적으로 늘어난다. 대표적으로 피보나치 수열이 있으며, 재귀가 역기능을 할 경우도 해당된다.

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

 

 

 

시간복잡도의 필요성

비효율적인 코드를 개선하는데 쓰이는 기준이 된다.
예를 들어 O(n^2)짜리의 알고리즘을 O(n)으로 줄인다면 코드의 성능이 향상됐다고 할 수 있다.
어떤 값을 집어넣어 9초가 걸리던 로직이 3초로 줄어든 것이니까

 

 

 

시간복잡도를 줄이는 법

1. 반복문의 숫자를 줄이는 것
2. 자료구조를 적절하게 이용하는 것
3. 알고리즘을 적절하게 이용하는 것

 

1. 반복문의 숫자를 줄이는 것

시간복잡도에는 반복문이 시간 소모에 가장 많은 영향을 끼친다. 그렇기 때문에 시간복잡도를 줄이는 첫번째 방법은 반복문의 숫자를 줄이는 것이다.

 

 

2. 자료구조를 적절하게 이용하는 것

 

3. 알고리즘을 적절하게 이용하는 것

아래표는 배열의 대표적인 정렬 알고리즘 시간복잡도를 나타낸다. 이진탐색, 그리디 등의 알고리즘도 있으니 더 알아보자.

 

공간복잡도(Space Complexity)

작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다. 하지만 최근엔 컴퓨터 성능의 발달로 메모리의 여유 공간이 충분해져서 공간복잡도의 중요성이 예전에 비해 낮아졌다. 시간복잡도의 경우, 최악의 알고리즘을 작성했을 경우 결과값이 나오지 않거나 무지하게 느린 속도로 실행돼서 최근엔 공간복잡도보다 시간복잡도를 더 우선시하여 프로그램을 작성한다.

 

int a = 10;

일반적으로 공간이 하나씩 생성되는 것을 1이라고 표현한다. 위의 공간복잡도는 O(1)이다.

 

public void main(int n) {
    int result = 1;

    for (int i = 0; i < n; i++) {
        result = result * 1;
    }
}

main() 메소드를 호출하면 변수 i와 result만 사용된다. 입력크기 n의 값과 상관없다. 이 경우 공간복잡도는 O(1)이라고 할 수 있다.

 

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

그러나 위 코드처럼 재귀함수일 경우엔 입력크기 n의 값에 따라 공간복잡도가 달라진다. 메소드 내부에서 n이 이 1이하가 될 때까지 factorial()메소가 재귀적으로 호출된다. 스택에는 n부터 1까지 쌓이며 공간복잡도는 O(n)이다.

재귀함수 같은 경우에는 함수 호출마다 그 함수의 매개변수, 지역변수, 함수의 복귀주소를 저장할 공간이 필요하기 때문에 해당 재귀함수를 반복문으로 변경할 수 있는 경우엔 반복문 사용이 공간복잡도 측면에서 더 효율적이라고 볼 수 있다.

 

공간복잡도를 결정하는 것은 보통 배열의 크기가 몇 인지, 얼마만큼 동적할당이 예상되는지, 재귀함수라면 재귀호출을 몇 번이나 하는지 등이 공간복잡도에 영향을 미친다. 프로그램에 필요한 공간은 크게 2가지로 나눌 수 있다.

 

1. 고정공간 (고정 되어있는 변수, 상수들을 위한 메모리 공간)
2. 가변공간 (매개변수, 지역변수)

 

 

 

📚 참고
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/#:~:text=%EC%98%88%EB%A5%BC%20%EB%93%A4%EC%96%B4%20%EC%9E%85%EB%A0%A5%EA%B0%92%EC%9D%B4%201%EC%9D%BC%20%EA%B2%BD%EC%9A%B0%201,(n2)%EB%9D%BC%EA%B3%A0%20%ED%91%9C%ED%98%84%ED%95%9C%EB%8B%A4.
https://www.inflearn.com/course/%EA%B0%9C%EB%B0%9C%EC%9E%90-%EB%A9%B4%EC%A0%91-cs-%ED%8A%B9%EA%B0%95/dashboard
https://coding-factory.tistory.com/609
https://coding-factory.tistory.com/608