7주차, 자료구조 개념, 빅오 표기법

1. 설명

효율적인 자료구조가 중요하다는 것은 우리 일상생활만 봐도 알 수 있다.

간단한 예로 우리는 라면을 만들면 그걸 컵에 담지 않는다. 또 만든 음식을 바로 먹을 게 아니라면

밀폐용기에 담아서 보관한다.

 

즉 데이터도 마찬가지로 종류와 용도에 따라 구분하는 게 당연한 것이다.

 

2. 자료(Data)와 자료구조 (Data Structure)

・ 데이터를 어디에 어떻게 관리할지

    ・  검색, 순회(iterate), 저장, 삭제, 변경...

・ 자료를 담는 추상적인 틀

 

・ 컴퓨터의 자원은 한정적이다.

・ 제한된 제약조건 내에 정확한 결과를 내야한다.

・ 데이터의 형태와 쓰임에 가장 적절한 자료구조를 쓰는 것은 매우 중요함

・ 모든 병목의 시작점

  ・ 잘못 쓴 자료구조 하나로 느린 시스템이 될 수도 있다. 

  ・ 거기다 트래픽이 몰리면 답도 없다.

 

3. 알고리즘

・ 어떤 문제가 주어졌을 때, 문제를 풀기 위한 동작들의 절차

    ・ 라면 끓이는 법, 집에서 학교로 가는 법 등

・ Input 값을 통해 Output 결과를 내는 법

 

 

빅오 표기법 

1. 설명

점근 표기법

・ 빅오(Big-O) 표기법

만약 7개의 공간이 있다고 치고, 찾고싶은 데이터를 가장 앞 칸부터 순회하면서 찾는다고 쳤을 때

하나를 찾는데 걸리는 시간이 0.1초면 최선(하한선)은 0.1초, 최악(상한선 / 절대 이거보다 높게 안나옴)

은 0.7초, 평균값은 0.4초 이 때, 들어가는 수마다 달라지고, 데이터의 개수에 따라 시간이 선형적으로

늘어난다. n개가 들어가면 O(N)의 시간복잡도를 가지게 된다.

 

  ・ 점근 표기법의 특징

      ・ 가장 영향력이 있는 항만 표시

          ・ O(N^3 + N^2 + N) -> O(N^3)

      ・ 상수항은 무시

           ・ O(2N + 1) -> O(N)

 

       ・ Big-O의 특징

             ・ O(1) < O(logN) < O(N) < O(NlogN) < O(N^2) < O(2^n)

 

    ・ 공간 복잡도

       ・ 데이터 관리에 필요한 공간

       ・ 데이터 양의 변화에 따른 공간의 변화

       ・ 예상 소요 공간 측정

 

     ・ 시간 복잡도

        ・ 데이터 처리에 소요되는 시간

       ・ 데이터 양의 변화에 따른 소요 시간의 변화

            ・ 수 만개 혹은 수 억개의 데이터를 처리해야 한다면 측정이 필요하다

       ・ 지연 장애 발생 시, 왜 발생했는지 찾을 수 있는 근거

 

세타 표기법, 오메가 표기법도 있지만 그리 많이 쓰진 않음