BigO 표기법과 시간복잡도

알고리즘의 성능을 판단하는 지표로는 시간복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있다. 시간복잡도는 알고리즘 수행시간을 의미하는 지표이며, 공간 복잡도는 알고리즘의 사용량을 의미한다.

반응형

알고리즘 성능 표기방법🤚🏻

• Big-O 표기법
  • 알고리즘의 성능을 수학적으로 표기해주는 표기법
  • 알고리즘 최악의 실행 시간과 사용 메모리를 표기
  • 가장 많이/일반적으로 사용함
  • 아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미
• 𝝮(오메가) 표기법
  • 알고리즘 최상의 실행 시간을 표기
• 𝜭(세타) 표기법
  • 알고리즘 평균 실행 시간을 표기

 

Big-O 입력값 표기 방법

• 만약 시간 복잡도 함수가 2𝑛² + 3n 이라면
  • 가장 높은 차수는 2𝑛²
  • 상수는 실제 큰 영향이 없음 
  • 결국 Big-O 표기법으로는 O(𝑛²)

 

시간 복잡도(Time Complexity)🕰️

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 걸리는 시간을 표현하는 방식입니다.

 

O(1)

• 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘입니다.

int func(int[] n){
	if (n.length <3) return 0;
	
	int a = n[0];
	a += n[1];
	a += n[2];

	return a;
}

 

O(n)

• 입력 데이터의 크기에 비례해서 처리 시간이 걸리는 알고리즘입니다.
• 표현식에 가장 큰 영향을 미치는 n의 단위로 표기입니다.

int func(int[] n){
	int s = 0;
	for (int i: n){
		s += i;
	}
	return s;
}

 

O(n²)

• 반복문이 두번있는 케이스입니다.

void bubbleSort(int[] n) {
	for(int i =0; i< n.length; i++) {
		for(int j=0; j<n.length; j++){
			...
		}	
	}
}

 

O(logn)

• 주로 입력 크기에 따라 처리 시간이 증가하는 정렬 알고리즘에서 많이 사용됩니다.

int sum(int[] n) {
	int sum = 0;
	int max = n.length;
	while (max > 0){
		sum += n[max -1];
		max /2;
	}
	return sum;
}

 

공간 복잡도란?🤔

• 알고리즘이 사용하는 자원 공간의 사이즈입니다.
• 공간 복잡도 = 고정 공간 요구 + 가변 공간 요구로 나타냅니다.
• 고정 공간은 입력과 출력의 횟수나 크기와 관계없는 공간의 요구입니다. (코드 저장 공간, 단순 변수, 고정 크기의 구조 변수, 상수)
• 가변 공간은 해결하려는 문제의 특정 인스턴스에 의존하는 크기를 가진 구조화 변수들을 위해서 필요로 하는 공간, 함수가 순환 호출을 할 경우 요구되는 추가 공간, 즉 동적으로 필요한 공간입니다.

공간 복잡도 예시

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

위 코드의 경우 n이 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;
}

다음 예시 코드에서는 n의 값에 상관없이 스택에는 n과 i 그리고 fac 변수만 저장되어, 여기서는 공간 복잡도는 O(1)입니다.

 

참고 자료
https://www.youtube.com/watch?v=6Iq5iMCVsXA
https://www.youtube.com/watch?v=QBZnX_P_dj4
https://www.bigocheatsheet.com/