시간복잡도 (Big-O)

빅오 표기법(Big-O Natation)

• 가장 빠르게 증가하는 항만을 고려하는 표기법
  • 함수의 상한만을 나타내게 됨

=> 빅오 표기법은 주어진(최선/최악/평균) 경우의 수행 시간의 상한을 나타낸다.

 

 

 

* (예제1) Fibonacci / non-optimized version

 

보통 피보나치 수열을 메모이제이션 안쓰고 이렇게 두번의 재귀호출을 이용해서 풀게 되면....

이렇게 이진 트리처럼 쭉쭉 만들어져서

O(n^3)보다도 더 가파르게 증가하는 O(2^n)의 시간복잡도를 가지게 됨. 

 

* (예제1) Fibonacci / optimized version

이렇게 중복해서 계산되는 부분이 없도록 memoization 기법을 써준다.

이렇게 고쳐준 코드로 수행하게 되면, 저 노란색 부분+ 검은색 부분은 실행될 필요가 없어지니까 결과적으로 시간복잡도는 O(N)이  됨.

 

* (예제2) Binary Search

 

한번 처리가 진행될때마다 검색해야 하는 데이터의 양이 반씩 줄어드는 알고리즘의 시간복잡도가 바로 O(logn).

 

 

 

** Big-O 판별해보기 퀴즈 -1

보통의 경우 O(n*2^n)아닌가 생각하기 쉬운데, 사실 계산해보면

이렇게 되기 때문에 결국엔 O(2^n)이라고 판별하는것이 옳다!!!

 

 

** Big-O 판별해보기 퀴즈 -2

sum의 값이 b로 초기화됐는데, 이게 a가 될때까지 while loop을 돌아야 함.

그런데 한번 while loop이 돌때마다 sum은 b씩 커짐.

즉, b->2b->3b ... 이런식으로 값이 증가함.

그렇기 때문에 while loop이 돌게 되는 횟수는 a를 b로 나눈 값의 몫이겠지!

 

** Big-O 판별해보기 퀴즈 -3

 

** Big-O 판별해보기 퀴즈 -4

 

** Big-O 판별해보기 퀴즈 -5

 

** Big-O 판별해보기 퀴즈 -6

     --> O(n)*O(n)이니까 O(n^2)

 

** Big-O 판별해보기 퀴즈 -7

한번 while loop 돌때마다 n의 값이 1/10씩으로 줄어듦! 따라서 O(logN).

 

** Big-O 판별해보기 퀴즈 -8

( 참고: mergesort의 시간복잡도는 O(nlogn) )

 

 

---

 

내용 출처 :

 

www.youtube.com/watch?v=6Iq5iMCVsXA&list=PLjSkJdbr_gFYSUYfnF_OGXtnGs2d3vWg7

www.youtube.com/watch?v=QBZnX_P_dj4&list=PLjSkJdbr_gFYSUYfnF_OGXtnGs2d3vWg7&index=5

 

freedeveloper.tistory.com/271?category=888096

[이것이 코딩 테스트다] 1. 코딩 테스트 출제 경향 분석 및 파이썬 부수기