Big-O 표기법

Big-O 표기법

---

알고리즘 성능을 수학적으로 표현하는것입니다. 

알고리즘에 답은 정해져 있지만 풀이 과정에는 답이 없습니다.  예을 들어 답이 10라고 할때 10이라는 답을 만드는 과정은 여러가지가 있습니다. 1+1+1+1+1+1+1+1+1+1 , 2 x 5, 20 / 2 , 15 - 5 등 여러가지 문제 풀이로 답 10을 구할수 있습니다. 여기서 10을 구할때 어떤 방식으로 빠르게 답을 구하고 시간을 단축시키느냐입니다. 

우리가 게임을 하려고 게임의 홈페이지 들어갔을때 그 홈페이지가 바로 들어가지고 빠르게 게임을 할수 있는 반면에

 10초뒤에 켜지든지 30초뒤에 켜지고 게임 들어가는 시간까지 5분 넘게 걸린다고 치면 누구나 화가 날수가 있습니다.

안에 있는 알고리즘이 얼마나 간략하고 중복이 없으며 시간 복잡도에 따라 달라질수 있습니다.

 

그걸 해결 하기위해 BIg-O 표기법이 뭔지 알아가는 과정입니다. 

 

 

 

O(1) constant time 표기법

---

F(int [] n) {
	return (n[0] == 0) ? true:false;
}

데이터의 크기와 상관없이 일정한 시간을 나타내는 알고리즘 입니다.

 

 

 

O(n) linear time

---

F(int [] n) {
	for i = 0 to n.length;
    	print i
}

데이터의 크기에 비례해서 처리시간이 걸리는 알고리즘 입니다. 

n의 게속을 늘리는 만큼 처리하는 시간이 늘어나는 알고리즘 입니다.

 

 

 

O(n2) quadratic time

---

F(int [] n) {
	for i = 0 to n.length;
    	for j = 0 to n.length;
    	print i + j;
}

데이터을 한개만 돌리는것이 아니라 두개을 돌리때의 모습입니다. 이렇게 각각 다른 for문을 돌리때 걸리는 시간복잡도를 O(n2) 라고합니다.

오른쪽 그래프 출처 : 엔지니어대한민국

 

 

 

O(nm) quadratic time

---

F(int [] n, int [] m) {
	for i = 0 to n.length;
    	for j = 0 to m.length;
    	print i + j;
}

데이터을 n만큼 돌리는게 아니라 n을 m만큼 돌리는 알고리즘이다. n만보고 n표기법이구나 하면서 실수가 많은데 변수을 잘보고 해야합니다. n은 많은데 m은 적을수도 있기 때문입니다.

오른쪽 그래프 출처 : 엔진니어대한민국

 

 

 

O(n3) polynomial / cubic time

---

F(int [] n) {
	for i = 0 to n.length;
    	for j = 0 to n.length;
        	for k = 0 to n.length;
    	print i + j + k;
}

오른쪽 그래프 출처 : 엔진니어대한민국

데이터를 2개가 아닌 3개 돌렸을때의 알고리즘 및 그래프 모습입니다. O(n3)는 O(n2)보다 한번더 돌리다 보니 그래프가 급격하고 상승하는걸 알수가 있습니다.