데이터 구조 및 알고리즘의 시공간 복잡도를 한눈에!!!!

 

안녕하세요~ 

 

요새 한참 장마철이라 비가 엄청 오네요.

 

일본에 비오는거 보니까 집이 완전히 고꾸라지는 장면도 뉴스에 나오던데요...

 

아무쪼록 이번 장마로 큰 피해가 없었으면 하는 바람입니다.

 

자, 오늘은 여러분들이 알고있는 대부분의 데이터 구조(Data Structures)와 정렬 알고리즘(Array Sorting Algorithm), 그래프연산(Graph Operation) 및 힙 연산(Heap Operation)에 대한 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complecity)를 Big-O 노테이션으로 계산한 값이 얼마나 되는지 한눈에 요약해서 알려드리고자 합니다.

 

우선 시공간 복잡도를 표시하기 위한 등급을 아래와 같이 색깔별로 나누었습니다.

 

 

초록색일 수록 좋은것이고 빨간색에 가까워 질 수록 끔찍하도록 안좋은 것을 의미합니다.

 

자, 그럼 데이터 구조에서 발생하는 연산과 관련된 Big-O 노테이션을 표로 정리한 것을 한번 보시죠.

 

 

와 ~ 하~ 우~

 

거의 모든 데이터 구조에 대해서 평균적으로 접근, 검색, 삽입, 삭제 등에 걸리는 시간 복잡도가 얼마나 되는지가 한눈에 나와있습니다. 

 

등급별로 색깔로 구분되어있어서 어떤 연산을 할 때에는 어떤 데이터 구조를 사용해야 할지가 한 눈에 보이는군요.

 

자, 그럼 이번에는 정렬 알고리즘에 대한 표를 한번 볼까요??

 

 

색깔별로 구분이 되어있으니 어떤 정렬 알고리즘이 가장 좋은지가 눈에 금방 들어오네요~~~

 

best(최선), average(평균), worst(최악)의 경우를 모두 보여주기 때문에 여러 사이트들을 뒤져가면서 찾아볼 필요가 전혀 없어서 좋네요, 그쵸? ㅎㅎ

 

이야~ 래딕스 정렬(Radix Sort)이 가장 빠른 속도를 자랑하는 군요!!!

 

그리고 퀵소트가 이름 값을 하지 못하는 것이 보입니다~ 아~ 안타깝네요~

 

자, 이번에는 그래프 연산에 대한 표를 한번 볼까요??

 

 

그래프에서 꼭지점을 추가하거나 삭제할 때 엣지를 추가하거나 삭제할 때, 값을 저장할 때, 조회할 때 각각 어느정도의 복잡도를 갖는지 쉽게 알 수 있습니다.

 

어떤 연산을 많이 사용하게될 지에 따라 해당 연산에 최적화되어있는 그래프를 선택하여 사용하면 될 것 같네요 ^-^

 

그러면 이번에는 힙 연산에 대한 시간 복잡도를 한번 알아보겠습니다.

 

 

Heap operation(힙 연산)은 거의 대부분 꽤 괜찮은 속도를 가지고 있네요. 

 

LinkedList(연결리스트)만 조심해서 사용하면 어떤 힙 구조를 사용해도 일반적인 프로그램에서는 아무 문제없이 돌아가겠네요.

 

자, 혹시!!! 저 Big-O 노테이션이 얼마나 빠른지 또는 얼마나 느린지에 대한 감이 안오시는 분들이 계실 수도 있을 것 같아서 Big-O 복잡도에 대한 차트를 또 준비했습니다.

 

아래 차트는 요소(element)수에 따라서 각각의 Big-O 복잡도가 얼마나 많은 연산(operation) 시간을 필요로 하는지를 그래프로 나타낸 것입니다.

 

 

저는 프로그램 개발을 할 때 요소수가 적은 경우에는 O(n^2)까지도 허용을 하지만 요소수가 많은 경우에는 가급적 O(nlogn) 이하의 복잡도를 갖도록 구현을 하고 있습니다.

 

아주 간단한 예를 들어 프로그램을 처음 배울 때 구구단 프로그램을 많이들 짜는데요. 

 

보통 for-loop를 중복사용해서 n^2의 복잡도를 보이도록 코딩을 하게 됩니다. 

 

하지만 조금만 더 생각해보면 아래와 같이 while-loop를 한번만 사용해서 구구단 코딩이 가능하다는 것을 알게됩니다.

 

(while-loop와 for-loop는 항상 상호 변환 가능하다는 것은 알고 계시죠? )

 

------------------------------------------------------

public class gugudan {

    public static void main(String args[]){

    System.out.println("구구단입니다.");
    int i=1,b = 1;

   while(i<10){
       if(b==10) {  i+=1; b=1;  }
       if(i!=10){
           System.out.println(i+"*"+b+"="+i*b);
           b++;
       }
   }

}

 

 

 

 

 

------------------------------------------------------

 

빅데이터 시대에는 알고리즘이 상당히 주목을 많이 받을 것으로 기대됩니다.

 

열심히 공부해서 미리미리 준비해 놓자구요 ^-^

 

모두 행복한 주말 보내세요~~

 

 

 

 

 

Reference : http://bigocheatsheet.com/