시간 복잡도

+ 한풀이)

안녕하세요! 어느덧 블로그를 시작한 지 1주일이 지났습니다! 

회사생활은 여전히 밋밋하고... 일할때도 머릿속은 코딩 생각밖에 안 나네요 ㅠㅠ 집 가서 무슨 공부를 해야 할까...

알고리즘, 웹, Git, 기타 컴퓨터 지식까지.... 할 일이 너무 많은 것 같아요...

하지만 이렇게 힘들어도 꾸준히 하다 보면 폭발적으로 실력이 늘어날 것이라 생각하고 계속해보겠습니다!!

 

오늘은 내가 짠 알고리즘이 좋은 알고리즘인지 판단할 수 있는 근거 중에 하나인 시간 복잡도를 공부했습니다.

 

주의! 비전공자로서 처음 개발 공부를 하는 것이라 내용이 틀리거나 부실한 것이 있을 수 있습니다!

댓글로 알려주시면 정정하도록 하겠습니다^^

 

먼저 시간 복잡도에 대해 알아보겠습니다.

같은 100개짜리 요소를 가진 리스트를 알고리즘을 돌렸을 때, A 알고리즘은 100초가 걸리고 B 알고리즘도 100초가 걸렸다고 가정해 봅시다. 그 후  200개짜리 요소를 가진 리스트를 돌렸을 때 A 알고리즘은 200초가 걸리고 B 알고리즘은 1000초가 걸렸다면? A 알고리즘보다 B 알고리즘이 시간 복잡도가 크다 라고 표현합니다. (A 알고리즘이 빠른 알고리즘이다!!)

 

이제 개념적인 부분을 한번 살펴보겠습니다.

알고리즘의 소요시간을 인풋 크기(리스트 길이)에 대해 나타낼 수 있습니다.

ex) n개의 요소를 가진 리스트에서 알고리즘 소요시간은 20n , n³ + 2n² +3, 20logn +20 등으로 나타낼 수 있습니다.

 

프로그래머들은 수식 하나로 알고리즘을 모두 표현을 못하기에 점근 표기법을 사용하기로 약속을 하였습니다! 점근 표기법의 가정은 N이 엄청 크다고 가정하는 것입니다! (위의 A, B알고리즘을 예 들었을 때처럼 n이 커질수록 좋은 알고리즘은 빛을 낸답니다!)

 

EX)

20n + 40 -> n의 영향이 큰 것 20n -> 계수(20)도 없애줌 O(n) [Big-O of n]

2n³ + 5n² +3 -> n의 영향이 큰 것 2n³ -> 계수(2)도 없애줌 O(n³) [Big-O of n³]

2lgN + 3 -> n의 영향이 큰것 2lgN -> 계수(2)도 없애줌 O(lgN) [Big-O of lgN]

 

위의 점근 표기법 예제에서,

2n³ + 5n² +3 에서 뒤에 5n² +3 을 왜 무시하는지 설명드리겠습니다!

 

먼저 n이 작을 때인 10을 가정한다면 2n³은 2000, 5n² +3은 503 입니다. 1500의 차이가 커 보이시나요?.?

그럼 n을 많이 키워서 10000을 넣어보겠습니다! 2n³ 은 2,000,000,000,000 으로 2조나 됩니다!

반면 5n² +3은 고작(?) 500,000,003으로 5억입니다 이제 둘의 차이는 1조 9995억 정도네요 ㅎㅎ

이처럼 n이 커질수록 고차항의 영향이 중요해져 저차항을 무시해도 지장이 없게 됩니다!

 

그럼 그다음 계수를 왜 무시하였는지 알아볼까요?

2차 함수의 계수를 아무리 낮게 하더라도 교점이 되는 n의 값이 커질 뿐 n이 아주 커지면 결국 고차 함수가 주요하게 작용합니다! 아래 그래프는 고등학교 때 그래프를 그려본다고 가끔 들어가던 지오지브라라는 홈페이지에서 그린 함수입니다.

 

위 그래프에서 보시는 바와 같이 x²의 계수가 아무리 낮아도 x가 커지면서 증가율은 일차함수 보다 큰 것을 확인할 수 있습니다 → 고차 함수의 계수는 무시 가능!