4. 자료구조와 알고리즘의 관계
알고리즘
- 컴퓨터에게 일을 시키는 명령어의 연속된 덩어리
- 컴퓨터에 의해 수행되기 위해 필요한 명령어의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것
- 사람(개발자)이 컴퓨터에게 일을 시키기 위해서 사람의 의도와 명령을 전달하기 위한 방법(언어/글)
알고리즘의 조건
- 출력
- 유효성
- 입력
- 명확성
- 유한성
5. 알고리즘 성능의 분석과 측정
실행시간 분석
- 알고리즘을 실행하는데 필요한 예측 실행시간을 추정하여 알고리즘의 성능을 분석
- 실행 시간의 예측
: 알고리즘의 실행 횟수를 O(n)이라고 표현
: 같은 O(n)을 가진다는 것은 실행 시간이 동일한 것이 아니라 실행 시간의 증가 경향이 유사하다는 의미임
실행메모리 분석
- 알고리즘을 실행하는데 필요한 공간(메모리)을 추정하여 알고리즘의 성능을 분석함
실행 메모리의 예측
- 알고리즘의 공간 복잡도(spacecomplexity)는 프로그램을 실행시켜서 완료하는 데 필요한 총 메모리 공간
- 고정 공간은 프로그램의 크기나 입출력의 횟수에 관계없이 컴파일 시에 결정되어 프로그램의 실행이 끝날 때까지 고정적으로 필요한 메모리 공간
- 가변 공간은 프로그램의 실행 과정에서 동적으로 할당되어야 하는 자료 구조와 변수들을 위해 필요한 메인메모리 공간
- Sp = Sc+Se (공간복잡도 = 고정공간 + 가변공간)
성능측정
- 컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간을 측정하여 알고리즘의 성능을 측정
- 실행 시간의 측정
: 실제로 실행 시간을 시계로 잰다는 것
: 실제로 실행될 수 있는 프로그램(실행 파일)이 있어야 함
: 시스템 시계를 이용
정리하기
- ‘자료’는 현실 세계에서 관찰이나 측정을 통해서 수집된 값(value)이나 사실(fact)입니다.
- ‘정보’는 어떤 상황에 대해서 적절한 의사결정(decision)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해설(interpretation)이나 자료 상호 간의 관계(relationship)를 표현하는 내용이라고 할 수 있습니다.
- ‘정보’는 어떠한 상황에 적절한 결정이나 판단에 사용될 수 있는 형태로 가공되거나 분류되기 위해 ‘처리 과정’을 거쳐서 정리되고 정돈된 ‘자료’의 2차 처리 결과물이다.
정보 는 자료를 처리(process)해서 얻어진 유용한 결과(result)라고 할 수 있습니다.
- 자료 사이의 논리적 관계를 컴퓨터나 프로그램에 적용하기 위해서는 자료의 추상화가 필요하며 추상화를 통해 자료의 논리적 관계를 구조화한 것을 자료구조(data structure)라고 합니다.
- 알고리즘이란 컴퓨터에 의해 수행되기 위해 필요한 명령어들의 유한 집합이 사람의 머릿속에 추상화되어 존재하는 것 입니다.
- 자료의 추상화와 구조화가 적절히 이루어지지 못하면 소프트웨어는 비효율적으로 수행되거나 소프트웨어의 확장성에 문제가 생길 수 있습니다.
- 추상화란 공통적인 개념을 이용하여 같은 종류의 다양한 객체를 정의하는 것입니다.
- 자료구조는 입력값의 추상화된 상태라면, 알고리즘은 컴퓨터가 수행해야할 명령의 추상화입니다.
- ‘미리 정의된 자료구조’는 프로그래밍 언어를 개발하는 개발자에 의해 정의되고 추상화되었고, 이를 컴퓨터내부에서 프로그래밍 언어의 형태로 구현된 자료구조를 의미합니다.
- ’미리 정의된 자료구조‘는 프로그래밍 언어 개발자가 프로그램 개발자를 위해 미리 정의하지만, ’사용자 정의 자료구조‘는 프로그램 개발자가 자신의 프로그램 개발 방향에 따라 프로그래밍 언어로 새롭게 정의하여 사용하는 자료구조입니다.
- 알고리즘이 가지고 있어야 할 조건들 ① 출력, ② 유효성, ③ 입력, ④ 명확성, ⑤ 유한성 등이 있습니다.
- 알고리즘을 실행하는데 필요한 시간과 공간을 추정하여 알고리즘의 성능을 분석(performance analysis)을 합니다.
그리고
컴퓨터가 실제로 프로그램을 실행하는데 걸리는 시간 측정하여 알고리즘의의 성능을 측정(performance measurement)합니다.