복잡도 계산

복잡도의 종류

• Time Complexity
• Space Complexity

 

---

복잡도의 정의

 

Time Complexity

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

 

Space Complexity

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

 

 

---

 

Example1)

다음과 같은 코드가 있을 때

 

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

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

 

 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)이다.

 

---

Example2)

다음과 같은 코드가 있을 때

 

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

 

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

---

 

Example3)

다음과 같은 코드가 있을 때

복잡도 계산은 다음과 같다

 

 

---

조건문의 복잡도 구하기

 

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

 

다음과 같은 코드가 있을 때

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

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

 

따라서 위의 코드는

Best Condition일 때 O(1)

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

 

 

---

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

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

 

 

 

---

Reference

www.youtube.com/watch?v=1U3Uwct45IY&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=5

www.youtube.com/watch?v=9TlHvipP5yA&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=6

www.youtube.com/watch?v=9SgLBjXqwd4&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=7

www.youtube.com/watch?v=p1EnSvS3urU&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=8