[알고리즘] 시간의 복잡도

lilyoh·2020년 10월 12일
0

시간의 복잡도는 알고리즘 수행에 얼마만큼의 시간이 걸리는지를, 공간의 복잡도는 얼마만큼의 메모리가 필요한지를 보여준다. 보통 시간의 복잡도가 더 중요하기 때문에 복잡도라고 하면 시간의 복잡도를 이야기한다.

복잡도를 표기하는 방법에는 여러 가지가 있다.

  1. 빅오 표기법
    최악의 경우 걸리는 시간을 표기하는 방법이다. ^는 제곱을 의미하며 빅오의 순서는 다음과 같다.
    O(1),O(logN), O(N), O(NlogN), O(N^2), O(N^3), ..., O(2^N), O(N!)
    오른쪽으로 갈수록 안 좋은 알고리즘이며, 보통 NlogN까지를 괜찮다고 한다. 최악의 경우를 뜻하므로 최선의 경우 O(1)이 나올 수도 있다.
    삽입정렬은 O(N^2)이다. 보통 O(N^2)는 안 좋지만 삽입정렬의 알고리즘이 간단하기 때문에 30개 이하 숫자의 경우에는 삽입정렬을 사용해도 괜찮다.

  2. 세타 표기법
    평균 걸리는 시간을 표기하는 방법이다. 최악의 경우가 일어나지 않는 알고리즘의 경우에 사용한다. 역시 Θ(N^2)부터는 안 좋다고 여겨진다. 평균이므로 최악, 최선의 경우가 없다.

코딩하면서 시간의 복잡도 줄이기!
: for문과 while문 등의 반복문을 3번 이상 중첩하여 사용하지 않는다.

참고자료

0개의 댓글