[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘(1) / Big-o 표기법

Big-O 표기법

BIG - O 표기법 1단계 : 대략적인 계산

- 수행되는 연산(산술, 비교 대입 등)의 개수를 '대략적으로'판단

 

 

BIG - O 표기법 2단계 : 대장만 남긴다.

 

규칙1) 영향력이 가장 큰 대표 항목만 남기고 삭제

규칙2) 상수 무시 (ex. 2N => N)

 

O(1 + N + 4 * N^2 + 1) 이런식으로 나와도 N^2임. 근데 이러한 표기 때문에 사실 같은 O(N)이라도 속도가 다를 수 있다는 것도 염두에 두고 있어야 함.

 

O(4 * N^2) => O(N^2)

 

O는 Order Of라고 읽는다.

 

재귀함수같은 경우엔 좀 복잡할 수 있지만, 대부분의 경우에는 산출하기 쉽다.

 

빅오 표기법의 의미?

=> 데이터가 늘어남에 따라 어떤 식으로 연산량이 증가하는 지 알고 싶은 것. N^2은 워낙 빠르게 증가하는 연산량인데, 그거에 비하면 나머지는 언급할 가치도 없을 정도로 영향이 미미하기에 생략한다. 

 

---

 

그래프 이미지.

https://github.com/cooervo/Algorithms-DataStructures-BigONotation/tree/master/images/graphs

 

컴퓨터 성능에 따라 당연히 연산 시간이 달라지니까 세세한수치가 중요한게 아니라, 비교를 해서 얼마나 속도차이가 나는지 보는 것이 중요하다.

 

n^2보면 성능이 끔직하다. (영상 10분 13초)

 

시간 복잡도를 얘기할 때는 뭐가 더 빠른지 정도는 머릿속에 그려져야 한다.

 

n^2, n^3은 정말 조심해서 사용해야 한다.

 

 

---

로그 함수란?

 

 

2^1 = 2

2^2 = 2 * 2 = 4

2^3 = 2 * 2 * 2 = 8

 

조금 더 일반화해서 2가 아니라 a라는 숫자로 일반화를 시키면

a^? = b

: a에서 몇 승을 곱했더니 b가 되었다라는 식이 성립될 때, ?가 log a (b)가 되는 것이다.

 

n log n 얘기할 때 보통 log밑에 숫자가 2인 경우를 말하게 된다.

 

도대체 log가 어느 상황에서 직관적인 표기법이냐? 에 대한 설명

: 예시가 이분탐색임 현재 상황에서 반씩 쪼개는 상황. 숫자가 N개가 있고, 한 번 탐색할 때 마다(찍을 떄 마다) 절반씩을 날리게 되니까 N/2처럼 계속 2를 나누게 된다. 

 

그러면 첫 번째 시도에서는 그냥 2를 나눈거고 두 번째에서도 또 2를나누니까

 

결국 알고 싶은 값은 N/2^?이 된다. (몇 번 2로 나누는 것을 트라이 했는지에 대한 횟수)

 

그러면 N/2^?이 대략 1이되었다고 가정하면 (근삿값) 식을 정리해보자. (1은 하나의 후보군?만 남았다라는 뜻)

N = 2^? 이 되면 된다.

 

그러면 2^? = N이 되는데 또 이건

? = log 2 (N)이 된다는 걸 알 수 있다.

 

결론적으로, 이분 탐색에서 몇 번쨰 트라이 만에 맞출 수 있냐는 log 2 (n)만에 맞출 수 있다는 것을 알 수 있다.

 

내가 설명을 이분탐색으로 너무 틀에 맞춘 느낌인데, 어떤 함수가 로그함수를 따른다고 했을 때, 반띵을 해서 후보군을 줄여나가는 이미지를 줄여나간다는 이미지를 떠올렸으면 좋겠다.

 

---