[lecture] 자료구조란

자료구조

자료구조란 컴퓨터에서 어떤 문제를 해결하기 위해 자료의 특성에 따라서 자료를 분류하고 구성하고 저장해 놓은 것을 말한다. 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 하기 때문에 자료구조는 중요하다.

알고리즘

이와 달리 알고리즘이란 문제해결방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서인데, 

• 입력(input) : 알고리즘 수행에 필요한 자료가 외부에서 입력으로 제공될 수 있어야 한다.
• 출력(output) : 알고리즘 수행 후 하나 이상의 결과를 출력해야 한다.
• 명확성(definiteness) : 수행할 작업의 내용과 순서를 나타내는 알고리즘의 명령어들은 명확하게 명세되어야 한다.
• 유한성(finiteness) : 알고리즘은 수행 뒤에 반드시 종료되어야 한다.
• 효과성(effectiveness) : 알고리즘의 모든 명령어들은 기본적으로 실행이 가능해야 한다.

위 조건을 충족해야 한다.

알고리즘의 성능을 분석하는 방법에는 1. 공간 복잡도 2. 시간 복잡도 가 있는데, 여기서 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간의 양인 공간 복잡도는 고정 공간과 가변 공간의 합으로 나타낼 수 있다. 중요한 건 시간 복잡도이다.

시간 복잡도란 알고리즘을 프로그램으로 실행하여 완료하기까지의 총 소요 시간을 말한다. 이는 컴파일 시간과 실행 시간의 합으로 나타낼 수 있으며 실행 빈도수의 계산을 의미한다. (for 반복문의 수행 빈도 수)

시간 복잡도를 표기하는 방법에는 빅-오(Big-Oh) 표기법을 사용한다. 1. 실행 빈도수를 구해 실행시간 함수를 찾고 2. 실행시간 함수의 값에 가장 큰 영향을 주는 n에 대한 항을 선택하여 3. 계수는 생략하고 O의 오른쪽 괄호 안에 표시한다.