자료구조와 알고리즘의 성능분석방법

자료구조 (Data Structure)

자료구조란 컴퓨터에서 처리할 자료들을 효율적으로 관리하고 구조한것이다.

자료구조는 데이터를 표현한다는데 표현한다는뜻에는 저장의 의미도 담겨져있다.

이렇게 자료들을 표현하면 그것들을 처리하는것을 알고리즘 이라고 한다.

그래서 알고리즘은 자료구조에 의존적이기도하다

자료구조에는 다음과 같은 구조들이 있다

자료구조를 크게 나뉘어보면 선형구조와 비선형구조, 파일구조와 단순구조로 나눌수있다.

자료구조에서 배울내용들은 선형구조와 비선형구조를 주로 다루기도한다.

또한 자료구조는 수학과 많은 연관을 나뉘어지며 특히 이수식을 잘 알아야한다.

x축이 데이터를 의미하고 y축이 연산의 횟수를 의미한다면 

과연 두 식중에 어떤게 더 효율적인가

아무래도 데이터가 많을수록 연산횟수가 적으면 좋은 프로그램일지않을까?

시간 복잡도(time complexity) & 공간 복잡도(space complexity)

그래서 알고리즘을 시간 복잡도(time complexity) 와 공간 복잡도(space complexity) 로 평가를 한다.

시간 복잡도란 속도에 해당하는 알고리즘의 수행시간 분석 결과이다.

공간 복잡도란 메모리 사용량에 대한 분석 결과이다.

왜 알고리즘을 평가하는데 공간 복잡도 보다 시간복잡도를 더 중요시할까?

그건 메모리의 크기보단 얼마나 더 빠른가를 중요시하기 때문이다.

같은 프로그램이 두개가 있어도 메모리의 공간을 따지는것보다

어느 프로그램이 더빠른지를 두고 사용하는게 더 효율적이기 때문이다.

그렇다면 어떻게 평가하는지 구체적으로 알아보자.

시간 복잡도를 평가할때는 

데이터의 수에 대한 연산횟수를 세어서 평가를하고 함수를 T(n)이라 한다.

시간복잡도를 또 두가지로 나눌수 있는데 그건 다음블로그에 설명하겠다.