[Algorithm] 시간복잡도 이해하기

1. 시간복잡도

1) 의미 : 알고리즘이 동작하는데 걸리는 시간을 대략적으로 나타냄 

🔎 코드는 최대한 간결하고 빠르게 작동하는 것을 원칙으로 한다.

 

2) 표기법

ⓐ O(Big O) :  시간의 상한 값(최악의 성능일 때 걸리는 시간)

ⓑ θ(theta) :  오와 오메가의 중간(평균)

ⓒ Ω(omega) : 시간의 하한 값(최고의 성능일 때 걸리는 시간)

 

- 보통 빅 O표기법을 씀

이유 : 알고리즘이 최악일 때 어떤 성능을 지녔는지 판단해야 사용유무를 판단할 수 있기 때문!

(어떠한 알고리즘이 최소 1의 속도가 걸린다고 해도 최악의 경우 N속도가 걸리면 무의미 함)

 

3) 대표적인 시간복잡도

- O(1) : 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다.

- O(log n) : 로그 시간 : 입력값 n 이 주어졌을 때, 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듭니다.

- O(n) : 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가집니다.

- O(n^2) : 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱입니다.

- O(C^n) : 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱입니다.

(출처 : [Algorithm] 알고리즘을 위한 시간복잡도 계산 방법 - Big-O 표기... (seolhun.github.io))

 

시간 : O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

 

4) 계산방법 : 명령이 끝날때마다 몇번 실행이 되는지를 계산함

✅ 원칙

- 가장 높은 차수만 남긴다

O(n² + n) -> O(n²)

- 계수와 상수는 버린다.

O(2n + 3) -> O(n)

 

✅ 예시

int main(){
    int a,b;
    scanf("%d %d", &a,&b);
    int result = a+b;
    printf("%d",result);
}

- 시간 복잡도 : O(1)

- 이유 :

a, b를 선언할 때(1) / a,b를 입력받을 때(1)/ a+b 계산(1)/ result에 대입(1) / result 출력(1) => 6 = 상수시간

* 대략적인 실행수임

---

int main(){
  int n;
  scnaf("%d", &n);
  for (int i = 0; i < n; i++)
  {
    // 필요한 코드 수행
  }
}

- 시간 복잡도 : O(n)

- 이유 : for문 위 두줄은 상수시간, 반복문으로 n번 실행되므로 시간복잡도는 O(N)이 된다.

---

//이중반복문
int main(){
    int n;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
        printf("*");
        }
    }
}

- 시간 복잡도 : O(n^2)

- 이유 : 수학계산하면 아래와 같다... 

다른 시간복잡도들도 위와 같은 방식(수학적인 계산)으로 도출할 수 있다.

---

 

5) 백준 시간제한

- 시간제한 1초라고 하면 대부분 1억번의 연산에서 1초가 걸리므로 1억번 연산 이내여야 함을 의미

- 따라서 시간복잡도를 계산하고 최대데이터수를 대입한다. 

ex) 데이터수가 10의 8승일 때(100,000,000) 시간복잡도가 n이면  1억번이 되므로 대략 1초가 걸림.

 

 

 

정리 끝!