1.자료구조와 알고리즘의 이해

자료구조란 무엇인가?

"프로그램이란 데이터를 표현하고, 그렇게 표현된 데이터를 처리하는 것이다."

 

데이터를 표현 : 자료구조

데이터를 처리 :알고리즘

 

자료구조의 분류

 

알고리즘을평가하는 두 가지요소 

- 시간 복잡도(time complexity) -> 얼마나 빠른가?

- 공간 복잡도(space complexity) -> 얼마나 메모리를 적게 쓰는가?

*시간 복잡도를 더 중요시 한다.

 

 

시간복잡도의평가방법

- 중심이되는 특정연산의 횟수를 세어서평가를 한다.

- 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다.

 

 

알고리즘의 수행속도 비교기준

데이터의 수가 적은경우의 수행속도는 큰 의미가없다.

데이터의 수에 따른 수행 속도의 변화정도를 기준으로한다.

 

최악의 경우와 최상의 경우

 

 

순차 탐색 예제

 

이진탐색 위키백과

 

이진 탐색 예제

 

이진 탐색 처리 결과 예제

 

 

 

 

참고: 윤성우의 열혈 자료구조