복잡도 계산

알고리즘

내일도무사히 2021. 1. 29. 18:07

메소드가 호출된 빈도를 세서 복잡도를 계산한다

알고리즘이 차지하는 총 공간.

다음과 같은 코드가 있을 때

복잡도 계산은 다음과 같다.

시간 복잡도 계산은 '메소드가 호출된 빈도'를 계산하는 것인데 위의 코드를 보면

s = 0, return s에서 메소드가 한번씩 호출되었고, for문의 조건이 'n+1'번이 호출되었고, for문 안의 S = S+A[i] 구문이 'n'번 호출되어서, 이를 다 합해 '2n+3' 이라는 값이 나왔고

가장 큰 지수의 값만 따지는 빅 오 노테이션을 통해 O(n)으로 표기했다.

공간 복잡도는 배열인 A가 n만큼의 크기를 가지므로 n의 값을 가지고 나머지 값들은 상수의 크기를 가지므로 1로 표기하여 다 합하면 n+3이므로, 공간 복잡도는 O(n)이다.

다음과 같은 코드가 있을 때

복잡도 계산은 다음과 같다.

중첩된 for문이므로 중첩된 for문에 시간복잡도가 곱해지는 것을 볼 수 있다.

다음과 같은 코드가 있을 때

복잡도 계산은 다음과 같다

조건문의 복잡도 같은 경우 조건문에 따라서 복잡도를 계산하게 된다.

다음과 같은 코드가 있을 때

if절이 실행된다면 O(1)

실행되지 않는다면 O(n)의 시간 복잡도를 가진다

따라서 위의 코드는

Best Condition일 때 O(1)

Worst Condition일 때 O(n)의 시간복잡도를 가진다고 볼 수 있다

그 외에도 다음과 같은 시간 복잡도들이 있다.

계산할때 Example3와 같은 표를 만들어 계산하면 편하다.