[자료구조 Java] 시간복잡도 (점근표기법, 빅오표기법)

시간복잡도란?

: 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계

▶︎ 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지 나타날 때 사용되며 보통 Big-O 표기법으로 표현

📍점근 표기법
1) Big-O(빅오) : 상한 점근, 시간복잡도가 최악인 경우
2) Big-Ω(빅오메가) : 하한 점근, 시간복잡도가 최선인 경우
3) Big-Θ(빅세타): 상한, 하한의 평균(중간값)
▶︎ 빅오표기법의 경우, 프로그램 실행 과정에서 소요되는 최악의 시간까지 고려하기 때문에 효율적인 코드의 판단 척도로 사용 가능

// 시간복잡도 10n^2+n을 가지는 경우의 코드
for (int i = 0; i < 10; i++) {
  for (int j = 0; j < n; j++) {
    for ( int k = 0; k < n; k++) {
        System.out.println(i+" "+j+" "+k);
    }
  }
}
for (int i = 0; i < n; i++) {
  System.out.println(i);
}

1-1. 시간 복잡도의 존재 이유는?

: 효율적인 코드로 개선하는 데 쓰이는 척도로 사용하기 위함
- 효율적인 알고리즘을 구현한다는 것은, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 의미

1-2. 시간 복잡도 속도 비교

1-2-1. O(1)

- Constant complexity : 입력값이 증가하더라도 시간이 늘어나지 않고 같음을 의미

int[] arr = {1, 2, 3, 4, 5};
int idx = 0;
System.out.println(arr[idx]); // 1

// arr에 들어있는 값이 증가하더라도, 시간복잡도는 바뀌지 않음

1-2-2. O(n)

- Linear complexity: 입력값이 증가함에 따라 같은 비율로 시간이 증가하는 것을 의미

// Case 1

int n = 1;
// n의 값이 1 증가할 때마다 연산의 수가 비례하여 증가.

for(int i = 0; i < n; i++) {
  System.out.println(i);
}


// Case 2
// 같은 비율로 증가하고 있다면, 연산이 2배씩, 5배씩, 10배씩 증가하더라도 O(2n)이 아닌 O(n)으로 표기.

int n = 1;

for (int i = 0; i < 2n; i++) {
  System.out.println(i);
}

1-2-3. O(log n)

- Logarithmic complexity: 입력 시간이 커질 때, 연산 횟수가 logN에 비례하여 증가하는 것을 의미
- 이진검색처럼, 원하는 value 값을 찾기 위해 반씩 나눠서 연산을 수행하는 것이 이에 속함

int n = 4;

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

1-2-4. O(n^2)

- Quadratic complexity: 입력 값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미

- 2n, 10n을 모두 O(n)으로 표기하는 것처럼, n의 3승, N의 5승도 모두 O(n^2)로 표기

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.println(i+" "+j);
  }
}

1-2-5. O(2^n)

- Exponential complexity: 입력 값이 증가함에 따라 연산수가 2^n에 비례하여 증가하는 것을 의미

- 재귀로 만든 피보나치 수열이 대표적으로 O(2^n) 시간복잡도를 가짐
- 구현한 알고리즘의 시간복잡도가 O(2^n)이라면 다른 접근방식을 고민해보는 것이 필요

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