시간복잡도와 빅오 표기법

시간복잡도

T(n) = n^2+n+1;와 같이 표시 한다.

입력 데이터의 개수 n에 대해서 이 알고리즘을 수행했을때 얼마만큼의 시간이 걸릴지 대략적으로 파악할 수 있다.

즉 만약 3개의 입력 데이터가 존재한다면 9+3+1=13 정도의 연산 횟수가 필요하다는 것이다.

이 시간복잡도를 통해서 이 알고리즘이 얼마나 오래 걸릴지 추정해볼수있다.

빅오 표기법(O(n))

위의 시간복잡도 함수 T(n)에서 사실 최고차항이 시간복잡도 계산에 가장 큰 영향을 미친다.

즉, 대략잡아서 보면 입력데이터 n의 개수가 늘어남에따라서 n^2+n+1중에서 n+1항은 어차피 이 함수의 결과에 영향을 덜 주기 때문에 최고차항만을 가지고 시간복잡도를 대략적으로 측정해보자는것이다.

그럴때 사용하는것이 빅오 표기법,세타 표기법, 오메가 표기법등등이 있는데, 그중에서 빅오 표기법이 가장 많이 사용된다. 빅오 표기법은 최악의 경우를 의미한다.

즉 위의 T(n)시간복잡도 함수를 갖는 알고리즘을 사용했을때 최악의 경우 n^2번 정도 연산을 수행한다는것이다.

이때 O(n^2)으로 표현하고, 말로는 빅오가 엔제곱이다라고 표현한다.

즉 입력데이터가 늘어남에따라 연산 시간이 어느정도로 증가 될까?를 대략적으로 파악하고 싶을때 사용하는 기호가 빅오 이다. 빅오가 엔제곱이라는것은 입력데이터가 늘어남에따라 y=x^2함수의 형태로 연산횟수,시간이 늘어난다는것을 의미한다.

정리하자면, 빅오라는것은 시간복잡도 계산에 가장 큰 영향을 미치는 항만을 기준으로 시간복잡도를 나타낸것이다.

시간복잡도라는것은 프로그램을 실행시켜서 완료될때까지 걸리는 시간을 의미한다.

빅오 표기법은 시간복잡도를 표시하는 하나의 방법이다.

즉 어떤 알고리즘의 최악의 경우의 실행시간을 대략적으로 표기해놓은 방법이다.

바이너리 서치 알고리즘은 빅오가 nlogn이야

-> 바이너리 서치 알고리즘은 n개의 원소가 있을때 아무리 못해도(최악의 경우에) nlogn번 정도(대략적) 반복문을 돌리면 값을 찾을 수 있어.