[자료구조&알고리즘]Big O 표기법 (빅오) #1

빅오란?

빅오는 대략적으로 숫자를 세는 것의 공식적 표기법이다 정식으로 입력된 내용일 늘어날수록 알고리즘에 실행 시간이
어떻게 변하는지 설명하는 공식적인 방식이다.
빅오는 어떤 펑션의 입력값이 늘어나는 것과 평션 실행 시간이 변하는 관계를 말한다
즉 코드와 코드의 성능을 다른 코드와 비교하는 방법이다.

단순히 돌아가는 코드는 실제로 규모가 매우 작은 프로젝트나 정적인 프로젝트에서는 큰 상관이 없을 수도 있다. 하지만 규모가 크고 셀 수 없을 정도의 데이터를 다루는 프로젝트를 하는 대기업 등에서는 성능이란 것은 큰 차이를 가져온다.

효율적인 코드 작성으로 시간을 아낄 수도 있고 명료한 코드로 유지보수가 용이할 수 있게 만든다.

이를 가능케 하는 것이 빅오 표기법이라 할 수 있다.

빅오 표기법

기본적으로 입력한 n이 커질수록 알고리즘이 얼마나 효율적인지표현 하는 방식

 

 

1번째 addUpTo 함수는 n이 커질수록 실행시간이 1:1 비율로 늘어나고 연산의 갯수는 n의 곱과 연결되어있다
2번째 addUpTo함수는  빅오가 1이라고 표현 할 수 있다
O가 있고 가로안에 1,n,n제곱,n log n..이런것과 연결되어있다
이 표기법의 의미는 n의 값이 커질수록  실행시간은 변하지않는다 

<빅오 표기법을 단순화 하는 방법>
-첫번째 산수는 상수라는 것 .덧셈,뺄셈,곱셈,나눗셈을 포함
-인덱스를 사용해서 배열 엘리먼트를 접근하는것 
-루프가 있으면 복잡도가 루프의 길이 곱하기 루프안에 있는 연산

 

2번째펑션은 항상 연산이 세개를 수행할 것이고 n이 어떤값이든 항상 똑같은 갯수일것 
그렇기 때문에 시간이항상 거의똑같다 선을 살표 보면 대략적으로 변화가 거의 없는 것을확인할 수있다

1번째 펑션은 실행해야할 연산의 갯수가 많다  n값이  커질수록 걸리는 시간이 n과 비례해서 선형으로 늘어나는 것을 볼수이있다

 

 

addupToFirst와 똑긑이 n이 늘어난다면 실행시간도 그만큼 들어남

n이 커질수록 실행시간이 n제곱의 값으로 늘어난다는 것

그래프로 표시해 보면 

빅O표기법 으로는

 

 

밑 그래프는 실행 시간이 n제곱의 값과 비례함

n이 커질수록 훨씬 더 커짐 n곱하기 n만큼 늘어나는것을 볼수있음

 

 

빅O표기법으로 표현해보면