데이터 구조 2 (Algorithm efficiency ,Stack, ADT)

• Algorithm efficiency

→ Time complexity : 알고리즘 실행시간에 대한 효율성을 평가하는 척도.

 

ex)

   n = 데이터 규모 (매우 큼) 

   ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

   Statement (A)

   for(n번){

     for (n번){

     Statement (B)

   }

   }

   for(n번){

   Statement (C)

   }

 

→ 이런 경우에는 각 Statements들이 몇 번 돌아간 지 보자.

       A = 1번 

       B = n^2

       C = n번

이고 이것들을 식으로 옮긴다면 

  →수행시간 f(n) = Bn^2 + Cn + A 이다.

 

 

이렇게 데이터 개수 n에 관련된 식이 나오면 최고차항의 지수만 고려하여 효율성을 판단하고,

그 방법을 Big - O natation이라고 한다.

위 같은 식은 O(n^2)으로 표현.

 

• Big - O natation  

       → 실행시간을 다항식으로 표현할 수 있을 때, 최고차항의 지수에만 관심 ...(계수는 필요 없다) 

 

               쓰이는 때 : 주로 데이터의 양이 많을 때

 

              ## 다항식 최고차항의 지수가 낮으면 낮을수록 효율적이다.

 

 

자주 나올 것 같은 Notation 식들 

 

- O( log n ) = log 함수에 비례하여 시간이 증가한다.

→ Tip : for문에서 i증가가 +가 아니라 *거나 / 일 때 

→         수행해야 할 작업들이 매 수행마다 반으로 줄어들 때 쓰임 = 당연함 제곱의 역이니까

 

ex)  for(n번 ... i=i+2) ... > (1/2)n > O(n) (지수는 상관없음)

     for (n번, k/2) ... > O (log n) 

 

 

 

코드를 보고 Big - O 짤 줄 알기 (반대도 되어야 함)

 

 

 

---

• Stacks ( 아마 시험에 Stacks 손코딩 시킬 수도 있을 것 같음 )

         →  Last in, First out 특성의 linear list    (linear = 순차적으로 하나하나)

 

  적용 연산 ( TOP에서 이루어짐 )

- Push  → Stack에 원소 하나 저장

- Pop   →  Stack에 원소 하나 Take  → Pop 해서 하나를 취하면 , 가장 마지막에 넣었던 원소를 얻음

- Create Stack : 스택 생성 →  Array 선언, top 값 초기화 ( 추가될 원소가 들어갈 곳 )

- Full_Check:  스택이 꽉 찼는가 확인 [ Push 할 때 쓰인다. ] →  Boolean 함수로 구현됨 / Top=>SIZE 면 에러

- Enpty_Check:  스택이 비었는가 확인 [ Pop 할 때 쓰인다. ] →  Boolean 함수로 구현됨 / Top==0 면 에러

 

# Push  → 1. Top 에 주어진 원소 넣기  → 2. Top 1증가 / [ 넣기 전에 Full인지 항상 체크 ]

# Pop  → 1. Top 1 감소 → 2.   Top 에 있는 원소 Return / [ Return 전에 Empty인지 항상 체크 ]

* Top 의 초기값을 0으로 하냐 -1로 하냐에 따라 달라짐

 

---

• ADT ( Abstract Data Type )

 

     -  Data type

     -  쓰임 : a set of data + operations (that can be performed on the data)

     -  Data structure : 데이터를 어떤 규칙에 의해 모아놓은  것 ( array , stacks , queues, trees)

 

 

• Abstraction 

→  어떤 Data type의 사용법'만' 명시 / 내부적인 구현 내용은 표시하지 않음.

   : 알 필요가 없는 건 알지 못하게 하여 개발과정의 효율성을 ↑

ex) 컴퓨터, 가전제품, math함수의 sin함수 →  구현법은 알지 못해도 사용법만 알면 문제없음

 

즉 Data type의 specification과                       implementation을 분리하여 고려

 

                    사양, 명세 = 사용법                       내부적 구현

         →쓸 사람은 이거만 알면 됨                      → 쓸 사람은 알 필요 없음

 

예) Stacks Functions- operations

 

stack create_stack(int n); // n개의 용량을 가진 stack 생성

void push(element x); // 현재 stack에 원소 x 추가

element pop( ); // 현재 stack에 원소 한 개를 삭제

bool stack_full( ); // 현재 stack 상태가 full인지 판단

bool stack_empty( ); // 현재 stack 상태가 empty인지 판단

 

이것들만 알고 코드 구현 못해도 그냥 쓰는 법만 알면 됨

 

 

출처 : 한동대학교 김호준 교수님 - 데이터 구조 PPT