시간 복잡도는 무엇이고 어떻게 구할까?

시간 복잡도란?

 

특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.

문제를 풀다보면 실행시간안에 알고리즘이 마치지 않았다고 정답으로 체크하지 않는 경우를 볼 수 있다.

따라서 시간 복잡도를 잘 체크하여 문제를 풀어야 한다.

 

 

 

빅오 표기법

 

원하는 답이 나오지 않는다면 최대 얼마만큼의 시간이 걸릴까를 측정하기 위해

사용하는 것이 빅오 표기법이다. (Big-O)

입력데이터(n)에 따라 어떤 결과가 나올지, 각각의 함수를 통해서 알 수 있다.

 

 

 

시간 복잡도의 대표적인 종류

 

1 : 입력자료의 수에 관계없이 일정한 실행시간 갖음

 

Log N : 입력자료의 수에 따라 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타나는 유형 ex)이진 탐색

 

N : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우

 

N log N : 이것은 주로 큰 문제를 일정한 크기를 갖는 문제로 쪼개고 (Log N), 다시 그것을 하나로 모으는 경우에 나타남

 

N² :  이중루프내에서 입력자료를 처리할때 발생함.

 

N³ :  얘는 삼중 루프내에서 입력 자료 처리할때 발생. 

 

 

 

시간 복잡도 계산하기

 

명령이 끝날 때마다 실행 횟수를 적어본다.

void Func(int *a, n)
{
  int i=0,j=0; //1
  for(i=0;i<n-1;i++){ //n
    for(j=i+1;j<n;j++){ //(n-1)*n
      if(a[i]==a[j])a[j]=0; //(n-1)
	}
}

이후 실행 횟수를 모두 더한다 2n²-2n+2  ->상수는 생략하고 최고차항만 생각한다. => O(n²)로 표기합니다.

 

 

추가로 재귀함수의 시간 복잡도는, 재귀 호출이 불리는 횟수라고 볼 수 있다.

int Factorial(n)
{
  if(n==1) return 1;
  return n*Factorial(n-1);
}

Factorial(n) ->Factorial(n-1)...->Factorial(2)->Factorial(1)

은 즉 O(n)의 시간 복잡도

 

 

 

 

 

문제를 풀어보자.

시간 복잡도가 O(n2)인 경우 ex 삽입 정렬, 버블 정렬

2750번: 수 정렬하기 (acmicpc.net)

2750번: 수 정렬하기

[Java] 백준 2750번 수 정렬하기 (tistory.com)

[Java] 백준 2750번 수 정렬하기

 

 

 

 

 

 

 

 

 

 

 

참고)

 

[Algorithm] 알고리즘 시간복잡도에 대하여 (tistory.com)

[Algorithm] 알고리즘 시간복잡도에 대하여

cafielo :: 시간복잡도 개념 및 구하기 (tistory.com)

시간복잡도 개념 및 구하기