C# - Big-O 표기법, 알고리즘 성능,척도

인프런 강사님 "Rookis" 님의 "[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘"를 수강하고
정리해보고자 쓴 글입니다. 잘못된 정보가 있을 수 있으니 참고용으로만 봐주시면 감사하겠습니다.
해당 글은 꾸준히 수정할 계획입니다. 감사합니다 :)

BigO 표기법은 면접에서 자주 등장하는 주제이므로 잘 알고 넘어가자!

서로다른 두 알고리즘을 비교하기 위해서, 즉 누가 더 성능이 좋은지 판단하기 위해서는 무엇을 기준으로 측정해야할까?

• 프로그램의 실행 속도를 비교한다.
  이 방법은 환경마다 (Ex. 컴퓨터 세팅차이, 운영체제, 디바이스) 다르기때문에 적절하지 않다.

• BigO 표기법을 사용한다.
  객관적으로 알고리즘의 성능을 표현할 수 있다.
  알고리즘의 효율성을 측정하기 위함.
  컴퓨터의 성능(환경)에 의존적이지 않고, 기준이 명확함.

BigO 표기법을 이용한 알고리즘 성능 측정 과정

• 1단계 : 대략적인 계산
  수행되는 연산(산술, 비교, 대입 등)의 개수를 대략적으로 판단한다.

public int Add(int N)
{
  return N+N;
}
  // 대략적인 연산 개수 : 1

public int Add2(int N)
{
  int sum = 0;
  for(int i=0; i<N; i++) 
  {
    sum += i;
  }
  return sum;
}
// 대략적인 연산 개수 = N 

• 2단계 : 제일 큰 차수만 남기고, 계수는 지운다.
  1. 제일큰 차수만 남긴다.
  2. 상수항과 앞에 붙은 계수는 지운다.

O(1 + N + 4*N^2 + 1)
= O(4*N^2) = O(N*2)

O(1)

대입, 산술, 비교를 한 번 할때를 연산 1회로 생각한다.

// 대입
int a = 0;
int b = 2;

// 산술
a += 3;

// 비교
if(a>b) {
}

O(N)

1차원 정수 배열안에 놓인 모든 값을 더하여 출력하는 알고리즘

int[] arr = new int[5];
int sum = 0;

// O(N)
for(int i=0; i<arr.length; i++) {
  sum = arr[i];
}

O(Log2(N))

업다운 게임은 숫자 1~100 사이에서
상대방이 생각하는 숫자를 맞추는 게임이다.
상대방이 생각하는 숫자가 35라고하면,
나 : 75 ?
상대 : 다운!
나 : 16 ?
상대 : 업!
나 : 36 ?
상대 : 다운!
나 : 31 ?
상대 : 업!
나 : 35..?
상대 : 정답!

이렇게 상대가 생각한 숫자가 내가 말한 수보다 작으면
상대방은 ‘다운’이라고 말하고, 크면 ‘업’이라고 말하여 상대의 숫자를 맞추는 게임이다.

내가 말하고 싶은 숫자를 하나씩 말해보면서 정답을 맞추기보다는 규칙적으로
찾아보면 수월할 것이다.
우리가 해볼 방법은 이진 탐색이다. 이 방법에 대해서는 추후에 구체적으로 알아보자.

상대방이 생각하는 숫자를 N 이라하고, 우리가 말할 값은 K라고하자.
1) K는 상대방이 생각하는 숫자가 있을거라고 생각되는 범위의 중앙값이다. (범위의 크기가 홀수라면 중앙값 - 1)
2) 만약 N<K (or N>K) 이라면 N보다 작은 값 (or N보다 큰값)들
사이에 N이 있다고 말할 수 없다.
따라서 N보다 큰값 (or 작은 값) 들이 우리가 N이 있을 범위라고 생각할 수 있다.

업다운 게임에서는 데이터 개수가 100이였다. 만약 데이터 개수를 N 이라하자.
데이터를 절반씩 나누어서 N = 1 or 1에 가까운 수가 될 때까지 나누는 ‘연산횟수’를 X 라고 하면

N/2^X = 1
N=2^X
X = Log2(N)

Big O 표기법의 의의

‘이 함수가 정확히 몇개의 연산을 한다’ 가 중요한 것이 아닌,
‘데이터가 늘어남에 따라 어떤식으로 연산량이 증가하는가?’ 이다.