Big O

이미지출처: https://danielmiessler.com/study/big-o-notation/

시작

만약에 바다건너에 사는 친구에게 파일을 보내야 한다면 나의 선택은?

=> 이메일, 혹은 클라우드와 같은 전송방식을 이용하겠지?

구지 파일을 주려고, 비행기를 타고 가서 줄까?

=> 아니.

만약에 파일이 100TB라면?

=> 아마 비행기를 타고가서 하드 드라이브를 주는 것이 훨씬 빠르겠지?(비용이 문제가 아니라면.)

시간 복잡도

이것을 점근표기법으로 나타낸 것이 바로 Big O Notaion 즉, Big O 라고 한다.

친구에게 온라인으로 파일을 보내는 것 : O(s).
=> s가 "파일 사이즈"라면, 파일 사이즈에 따라 실행시간이 더 걸림(선형적:linear time)

비행기로가서 하드 드라이브를 주는 것: O(1).
=> 파일 사이즈에 상관없이, 그냥 일정한 시간이 걸림(상수시간:constant time)

상수가 얼마나 크든지, 선형시간이 얼마나 느리게 증가하는지에 상관없이 어느시점부터는 O(n)은 O(1)의 실행시간을 넘어선다.

O(log n), O(N log N), O(N), O(N^2), O(2^n)같은 것들도 있지만 딱 정해진 리스트는 없음.

벽에 페인트를 칠해보자

넓이가 "w" 높이가 "h"인 벽에 페인트칠하는 시간 복잡도를 계산해보면 O(wh)가 되겠지.
이 벽에 페인트를 "l"번 만큼 더 덧대어 발라야 한다면 시간복잡도는 O(whl)이 될것이다.