1장 자료구조와 알고리즘의 이해 - 순차 탐색 알고리즘 -

 * 자료구조를 공부하면서는 그림으로 많이 그려보는 것이 필수다!

1. 자료구조란? 

 - 데이터를 표현-자료구조하고, 표현 된 데이터를 처리-알고리즘하는 것이다.

  즉, 다시말해서 자료구조를 정의하면 알고리즘으로 처리하는 것이다.

  예를 들어 데이터를 표현한다는 것은 int 형, char 형 등등을 선언하는 것이 될 것이고,

 그렇게 선언 된 데이터를 가지고 처리하는 것이 알고리즘이다.

 - 알고리즘은 자료구조에 의존적이다.

2. 알고리즘의 성능분석 방법 

 - 지수식 y = 2^x    과   로그식 y = log2x

   여기서 알아둘 것은 

이 식을 가지고 로그식이 데이터 처리하는 것에 있어서 좋은 방식이다! 라는 것을 아는 것이다.

 - 시간복잡도(Time Complexity)와 공간복잡도(Space Complexity)

  시간복잡도 : 얼마나 빠른가? == CPU의 연산이 얼마나 부담되느냐?

  공간복잡도 : 얼마나 메모리를 사용하는가?

  시간복잡도의 평가방법을 주로 알고리즘의 성능으로 평가하는데 

 - 첫번째 방법은 연산의 횟수를 세는 것이고,

 - 두번째 방법이 t(n) = n 으로 보고 평가하는 것이다.

                     

                                 <그림 2> t(n) = n    ==   최악의 경우(Worst Case)

 - 그림 2를 통해 알 것은 알고리즘 A가 좋다는 것이다.

 - 함수로 정의하는 이유는 위와같이 그래프를 쉽게 이해할 수 있기 때문이다.

 - 그럼 평균의 경우를 구하면 되지 않는가?!

  하지만, 그런 경우는 평균이 무엇이 될 것이냐를 두기가 힘들고, 신뢰도가 높지가 못하다.