*인프런의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 복습하기 위해 정리한 글입니다.
우리가 알고리즘을 연구하는 이유는 좀 더 효율적인 코드를 위해서다.
그러기 위해선 사용하려는 알고리즘의 효율성이 기존보다 더 좋다는 것을 입증해야 한다.
알고리즘의 효율을 측정하기 위해서는?
- 실행 속도 비교? => 환경에 의존적
- 입력(데이터)이 적은 구간과 많은 구간에서 성능이 확연히 차이가 날 경우? => 일관적으로(?) 효율적이지 않은 상황
그래서 대안으로 객관적인 Big-O표기법을 사용한다.
1. 수행되는 연산(산술, 비교 대입 등)의 개수를 '대략적으로' 판단한다.
2. 영향력이 가장 큰 대표 연산만 남긴다. 상수는 무시한다.
위 코드를 Big-O표기법으로 작성하면
O(1 + N + N² * 4 + 1) 이 된다.
여기서 영향력이 큰 항목만 삭제해서 표기를 하면
= O(N² * 4) = O(N²) 이 된다. (*O는 Order of라고 읽는다.)
그럼 이 짓을 왜 하나? Big-O표기법의 의의가 무엇인가?
아래 그래프 표는 입력 N의 크기에 따라 성능이 영향을 받는 정도를 보여준다.
N²은 값이 클수록 정말 끔찍한 성능을 갖는다.
Big-O 표기법으로 작성해서 보면 그 코드의 성능이 대체적으로 어느 정도인지 짐작 가능하게 한다.
* 추가적으로 O(Log N)과 O(N)의 차이를 설명.
나는 0~100(0 ~ N) 숫자 중에 85를 찾아야 하는 게임을 하고 있다.
방법이 두 가지 있다.
1. 모든 숫자를 다 언급한다.
2. 0~100의 중간값인 50을 Up Down하여 0~50의 범위는 날리고, 51~100 의 중간값인 75를 업다운하면서 범위를 줄여나간다.
보통은 방법2를 선택할 것이다. 더 효율적이기에!
방법2를 식으로 표현하자면 N/(2^?) → 1이 된다.
=> ?는 내가 시도한 횟수. ?가 클수록 1에 수렴. 하나의 결과에 가까워 진다는 뜻.
N = 2^?이 되고 양옆에 Log를 붙이면 그것이 ? = Log N 이 된다.
즉 O(log N)의 효율을 가지는 알고리즘.
방법 1은 하나씩 다 건드려보는 방법이므로 ? = N이고, 그냥 O(N)이다.
그래프에서 보여지는 것 처럼 O(LogN)이 O(N)보다 더 효율적이다!