Big-O 표기법

big-O notaion

자료구조나 알고리즘에서 성능(효율성)을 측정하기 위한 지표

 

알고리즘의 효율성 = 데이터가 n개 주어졌을 때 사칙연산과 같은 기본 연산의 횟수

 

 

 

big-O notaion

빅오표기법의 정의

어떤 양수 n0, c이 존재할 때 f(n)= O(g(n)),
n0 이상의 모든 n에 대해 f(n) <= cg(n)

예를 들어보자

 

f(n) = n 이라고 하면

g(n) = n, c = 1 이라고 하면 c*g(n) = n

==> f(n) <= c*g(n)   

==>  n   <= 1*n

==> f(n) = O(g(n)) = O(n)

따라서 n의 빅오표기법은 O(n)이 된다

(만약 여기서 g(n) = 2n, c = (1/2)n이라고 하면 빅오 표기법은 O(2n)이 된다)

 

f(n) = 2n 이라고 하면

g(n) = n, c = 2 이라고 하면 c*g(n) = 2*n

==> f(n) <= c*g(n)

==>  2n   <= 2*n

==> f(n) = O(g(n)) = O(n)

따라서 n의 빅오표기법은 O(n)이 된다

 

f(n) = (1/2)n 이라고 하면

g(n) = n, c = 2 이라고 하면 c*g(n) = 2*n

==> f(n) <= c*g(n)

==>  2n   <= 2*n

==> f(n) = O(g(n)) = O(n)

따라서 n의 빅오표기법은 O(n)이 된다

 

 

다음과 같은 예시에서는 몇가지 빅오표기법의 특징을 알 수 있다

 

빅오표기법의 특징

1. 상수항 무시: 빅오표기법은 데이터 입력값이 충분히 크다고 가정-> 상수항 같이 사소한 부분은 무시한다   O(2n) --> O(n), O(6*n^2) --> (n^2)

2. 영향력 없는 항 무시: 빅오표기법은 데이터 입력값이 충분히 크다-> 가장 영향력 큰 항 이외의 항들은 무시 O(n^2 + 2*n+1) --> O(n^2)

 

빅오표기법 성능비교

빅오표기법의 성능을 비교한 그래프이다

fast : O(1) < O(log n) < O(n) < O(nlogn) < O(n^2) < O(2^n) : slower

 

각각 표기법의 예제들을 몇개씩 알아두면 유용할 것 같아서 적어두도록 하겠다

 

• O(1) : 기본 사칙연산, stack push,pop
• O(logn) : 이진트리
• O(n) : for문
• O(n logn) : quick sort, merge sort, heap sort
• O(n^2) : 이중 for문, insertion sort, bubble sort, selection sort
• O(2^n) : 피보나치 수열

시간복잡도

코드가 답을 도출하기까지 걸리는 시간을 나타내는 것

알고리즘의 수행 시간이 얼마인지를 빅오표기법으로 나타낸다

시간복잡도를 얼추 구하기 위해서는 1초에 대략 1억번의 연산을 한다고 가정한다

 

예를 들어 1부터 n까지 정수를 더하는 문제를 풀어본다

 

https://www.acmicpc.net/problem/8393

 

이 문제는 나는 2가지로 풀어 보겠다

 

#include<iostream>

using namespace std;

int main()
{
	int n, sum = 0;

	cin >> n;

	for (int i = 0; i <= n; i++)	//for문이 1번 사용되고 덧셈이 1번이므로 1*n번
	{
		sum += i;
	}

	cout << sum << endl;

	return 0;
}

위의 예제는 시간복잡도가 O(n)임을 간단하게 알 수 있다

 

다음은 수학공식을 이용해서 풀게 되면 (1부터 n까지의 합 = 1/2*n*(n+1))

 

#include<iostream>

using namespace std;

int main()
{
	int n, sum;

	cin >> n;

	sum =  n * (n+ 1)*0.5;	// 사칙연산이 1번있다

	cout << sum << endl;

	return 0;
}

위의 예제의 시간복잡도는 O(1)임을 알  수 있다.

곱셈이 2번 덧셈이 1번 있지만 연산은 3번하므로 시간복잡도는 O(1)임을 알 수 있다.

참고로 대입, 입력 드의 연산들은 다 제외하고 대충세도 맞아 떨어진다.

 

 

공간복잡도

알고리즘의 공간이 얼마나 필요로 하는지 나타낸다

크기가 n인 배열을 만들면 공간복잡도는 O(n)이 된다

크기가 n^2배열을 만들면 공간복잡도는 O(n^2)이 된다

 

 

 

참고 사이트 : https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란

참고 사이트 : https://kks227.blog.me/220781557098

스택(Stack) (수정 2019-05-14)