Big-O

* What is Big-O?

Mathematical notation that describes algorithm efficiency

시간과 공간 복잡도를 표현할 수 있다.

Describes the growth rate of algorithms

상수는 버린다(데이터가 증가함에 따른 증가율을 보기 위해 계산하기 때문)

 

* O(1) : constant time

data의 크기가 커져도 성능에 변화가 없다.

* O(n) : for문 같은 경우

data의 크기가 커지면서 시간도 비례적으로 증가한다.

*O(n^2)

* O(n*m) : quadratic time

* O(n^3) : polynomial / cubic time

ex. 삼중 for문

* O(2^n) : exponential time

ex) 피보나치 나선형

출처 : youtube 엔지니어대한민국, 빅오표기법 완전정복

길이가 1인 정사각형부터 시작해서 오른쪽 길이 1을 가지는 정사각형을 그리고,

위쪽 길이 2를 기준으로 모든 변이 2인 정사각형을 그리고,

왼쪽 길이 3을 기준으로 모든 변이 3인 정사각형을 그리고,

아래쪽 길이 5를 기준으로 모든 변이 5인 정사각형을 그리는 식으로 반복.

출처 : youtube 엔지니어대한민국, 빅오표기법 완전정복

피보나치는 n번째 수가 (n-1)번째 수 + (n-2)번째 수이므로,

매번 호출할 때마다 두 번씩 호출한다.

출처 : youtube 엔지니어대한민국, 빅오표기법 완전정복

 

* O(m*n)

 

*O(logn) 

ex. binary search

가운데 값을 찾아 더 적으면 앞 데이터를 보고, 더 크면 뒤쪽 데이터를 본다

한 번 처리할 때마다 검색해야 하는 데이터의 양이 절반으로 줄어든다.

데이터가 증가해도 성능이 크게 차이나지 않는다.

 

* O(sqrt(n))

 

출처 : youtube 엔지니어대한민국, 빅오표기법 완전정복