자료구조와 추상데이터타입(자바)

'자료구조'는 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체를 의미한다.

데이터를 정돈하는 목적은 프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서이다. 따라서 자료구조를 설계할 때에는 데이터와 연산들을 함께 고려하여 설계 해야 한다.

 

추상데이터타입(Abstract Data Type)은 자바 언어와 같은 객체지향 언어의 인터페이스 개념과 유사하다. 

인터페이스의 역할은 이렇다. 어떤 객체가 있고 그 객체가 특정한 인터페이스를 사용한다면 그 객체는 반드시 인터페이스의  메소드들을 구현해야 한다. 
만약 인터페이스에서 강제하고 있는 메소드를 구현하지 않으면 이 에플리케이션은 컴파일 조차 되지 않는다.

 

알고리즘의 성능은 수행시간을 나타내는 시간복잡도와 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타내는 공간복잡도에 기반하여 분석한다. 대부분의 경우 시간복잡도만을 사용하여 알고리즘의 성능을 분석하는데, 주어진 문제를 해결하기 위한 대부분의 알고리즘들이 비슷한 크기의 메모리 공간을 사용하기 때문이다.

따라서 알고리즘의 시간복잡도는 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 입력 크기의 함수로 나타낸다. 기본 연산이란 데이터간 크기 비교, 데이터 읽기 및 갱신, 숫자 계산 등과 같은 단순한 연산을 의미한다.

 

시간복잡도 분석은 최악의경우 분석, 평균경우 분석, 최선경우 분석, 상각분석으로 분석 할 수 있다.

 

일반적으로 알고리즘의 수행시간은 최악경우 분석으로 표현한다.최악경우 분석은 '어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다'라는 상한의 의미를 갖는다. 평균경우 분석은 입력이 무작위로 주어진다고 가정한다. 최선경우 분석은 가장 빠른 수행시간을 분석하는 것이다. 상간분석은 일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행시간을 분석하는 방법으로 특정한 상황에 최악경우 분석보다 현실적인 분석 방법이다.