[알고리즘] 빅오 표기법 (Big O notation)

알고리즘에서 복잡도를 판단하는 척도중 시간 복잡도와 관련이 있는 표기법 입니다.

빅오(Big O)표기법은 알고리즘의 최악의(최대소요시간)을  표현하는데 사용합니다.

 

*추가 정보*

빅오와 관련하여 빅오메가(Big Ω) , 빅세타(Big θ)의 표현법도 있습니다.

• 빅오메가 표기법 : 알고리즘의 최고(최저소요시간)을 표현합니다.
• 빅세타 표기법 : 알고리즘의 평균소요시간을 표현합니다.

다시 본론으로 돌아와 빅오 표기법에 대하여 알아보도록 하겠습니다.

빅오 표기법의 특징

1. 상수항 무시 : 알고리즘이 O(N+5)의 복잡도를 가졌다면 상수를 생략하여 O(N)으로 표기합니다.
2. 계수도 무시 : 알고리즘이 O(3N)의 복잡도를 가졌다면 계수를 생략하여 O(N)으로 표기합니다.
3. 최고차항 표기 : 알고리즘이  O(3N^3+2N^2+N+5)의 복잡도를 가졌으면 O(N^3)으로 표기합니다.

출처 : https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%85%EC%98%A4-%ED%91%9C%EA%B8%B0%EB%B2%95big-O-notation%EC%9D%B4%EB%9E%80

빅오 표기법의 종류 (Comparing Big O functions 이미지 참고)

1. O(1) : 입력값이 증가하더라도 실행시간이 동일할 경우 입니다. index로 접근하여 바로 처리할수 있는 연산 과정의 시간 복잡도는 기본 연산 수와 같습니다.(가장빠른X 항상같은속도일때) ex) 스택의 push, pop 
2. O(log N) : 연산이 한 번 실행될 때 마다 데이터의 크기가 절반 감소하는 알고리즘 입니다.(log 의 지수는 항상 2) ex)이진탐색 알고리즘, 트리 형태 자료구조 탐색
3. O(N) : 입력값(N)이 증가함에 따라 실행시간도 선형적으로 증가하는 알고리즘 입니다. ex)1중 for 반복분
4. O(N log N) : O(N) + O(log N)의 알고리즘의 중첩입니다. ex) 퀵, 병합, 힙정렬
5. O(N^2) : O(N) + O(log N)의 알고리즘의 중첩입니다. ex) 2중 for 반복문,  삽입, 버블정렬, 선택정렬
6. O(2^N) : 빅오표기법중 가장 최악의(느린)시간 복잡도입니다. ex)재귀 알고리즘, 피보나치수열

피보나치 까먹고있어서 다시 코드를 가져와 복습한다!

int Fibonacci(int n) // 피보나치
{
	/*
		0 1 1 2 3 5 8 13 21  -> 오른쪽의 마지막 2개숫자를 더해서 다음 숫자를 만드는 규칙
		0
		0 + 1 = 1
		1 + 1 = 2
		1 + 2 = 3
		n = (n -1) + (n - 2)
		(n -1) = (n -2) + (n - 3)
	*/

	// 피보나치 수학적인 풀이 void Fibonacci(int n)
	/*
		int n1 = 0, n2 = 1, n3;
		if (n == 1) // 입력값이 한개일때
			printf("%d ", n1);
		else
			printf("%d %d ", n1, n2);
		for (int i = 2; i < n; i++)
		{
		n3 = n1 + n2;
		printf("%d ", n3);

		n1 = n2;
		n2 = n3;
		}
	*/

	// 피보나치 재귀함수 사용 int Fibonacci(int n) => 반환값이 생겼기때문에 int로 변경
	if (n <= 0)
		return 0;
	else if (n == 1)
		return 1;
	return Fibonacci(n - 1) + Fibonacci(n - 2);
}