[알고리즘] 시간 복잡도 판단하기

시간 복잡도란?

입력값과 문제를 해결하는데 걸리는 시간과의 상관관계이다.

입력값이 2배로 늘어났을때 문제 해결하는데 걸리는 시간은 몇배로 늘어날까?

입력값이 늘어나도 걸리는 시간은 덜 늘어나는 것이 좋은 알고리즘이다!

---

각 줄이 실행되는 걸 1번의 연산이 된다라고 생각하고 계산한다

위 코드에서 연산을 보면

array의 길이 * array의 길이 * 비교 연산 1번

그러면 N * N 만큼의 시간만큼 걸렸다고 할 수 있다.

 

위 코드에서 연산을 보면

max_num에 array[0]을 넣는 대입연산 1번 + array의 길이 * (비교연산1번 + max_num에 num을 넣는 대입연산 1번)

1 + N( 1+1)  = 1 + 2N

 

이 시간 복잡도는 n이 커질수록 확연한 차이가 난다.

상수는 고려하지 않아도 된다. (크기 차이가 크지 않아서)

 

결국 시간 복잡도가 간단하고 수가 적은 것이 좋은 알고리즘이다.