Big - o 가 무엇이고, 어떤 실익이 있지? (feat. 알고리즘 효율성 측정, 입력(N)’ 에 따른 ‘부하(Time)’ 정도 )

Big - o 를 직관적으로 이해하고 , 사용시 실익이 무엇인지 알아보자.

 

 

Big - O 표기가 뭔데?

'알고리즘' 의 '효율성' 을 측정하는 '기준' 중 하나.

 

Big - O 가 왜 필요한데?

알고리즘을 쓰는 이유? 

더 '효율적' 이기 위해 ex) 더 많은 사람이 웹으로, 더 빨리 계산하기, 더 정확하게 계산하기

 

그러려면, 어떤 알고리즘이 더 효율적인지 '비교' 가 필요.

비교를 하려면 ‘기준’ 이 필요함.

 

그러면, ‘어떤 기준으로 알고리즘 성능을 비교’ 할 수 있을까?

가장 쉽게 생각할 수 있는 건, ‘시간 측정’

 

 

하지만 '시간 측정' 시 몇 가지 문제가 있음. 

첫 번쨰, ‘환경’ 변수.

동일한 알고리즘이라고 해도, 다른 환경(다른 PC, 다른 CPU, 다른 네트워크 등) 속도가 다르게 측정됨. 따라서 '속도 차이' 가 '알고리즘에 의한 건지, 환경 때문인지' 불명확해짐.

 

두 번째, '입력 구간별 성능 차이' 문제

(설령 동일한 환경 이라고 해도) 알고리즘이 ‘입력이 많은 구간, 입력이 적은 구간’ 별로 성능차이를 보임.

ex) 입력(인자, 인풋 데이터) 가 적은 경우 A 알고리즘이 우세, 입력이 많은 경우 B 알고리즘이 우세

(이 그림을 보면, 초기 n 에서는 nlogn 이 우세하나, n 이 커지면 1 이 가장 우세한 것을 알 수 있음.

 

 

그러면 어째?

시간 측정의 대안이 바로 Big - O 임.

 

 

여기서 잠시 의문

근데, big - o 표기법도 y 축이 time 이니까, 결국, '시간' 으로 보는거 아냐? ❓❓❓

음… 잠시 고민해보면,

자잘한 요소를 제외하고, 큰 차원, 에서 시간에 영향을 주는 요인을 제거? 하자는 건가?

 

 

그러면 BIG - O 를 어케 쓰는 건데?

[1단계] ‘연산’ 의 ‘개수’ 를 ‘대략적’ 으로 계산

산술 연산, 대입 연산이건, ‘연산’ 의 개수를 센다.

( [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘) 참고

 

[2단계] ‘BIG’ 만 남긴다.

1️⃣ ‘연산 덩어리들’ 중에서 ‘대장’ (가장 영향력이 큰 놈) 만 남긴다.

2️⃣ 그 ‘대장에게 붙어있었던 상수’ 를 떼어낸다.

 

이렇게 하는 이유는 ‘정확한 시간 계산’ 에 목적이 있는 것이 아니라, ‘특정 데이터가 주어졌을 때, 연산량이 어떻게 증가하는가.’ 를 알고 싶기 때문.

 

( [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘) 참고

 

 

이렇게 BIG - O 표기를 하면, 어떤 실익이 있나? (어떤 시사점이 있나? 어떤 의의가 있나?)

 

‘입력(N)’ 에 따른 ‘부하(Time)’ 정도를 알 수 있음. (⭐⭐⭐ 그래프를 기억)

BIG - O 표기를 하면, ‘특정 입력’ 일 때, 어느 정도의 ‘부하’ 가 오는지를 알 수 있음.

(중요하니까, 그래프 좀 더 상세히! ⭐⭐)

 

부하의 정도를 알면 뭐가 좋아? 어떤 상황에서 쓰여? (나의 뇌피셜🤯)

◼ 회사의 ‘인풋 데이터 범위’에 따라서 사용해야 하는 알고리즘이 달라짐.

EX) DAU 가 10,000 인 회사에서 돌아가는 알고리즘이 DAU 1,000,000 인 회사에서는 안 돌아갈 수도 있음.

◼ 아, 내 코딩이 지금 '부하' 가 많이 걸리네 -> 어떤 알고리즘이 원인이지? (문제 원인 파악)

◼ 아, 이 알고리즘을 사용하면, 제곱이 있으니까 -> 부하가 많이 걸리겠네? (예측)

 

---

참고한 자료 🔗 

( [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘) 참고

https://inf.run/bEFb

[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 - 인프런 | 강의