(자료구조론 필사) 1장 기본개념

**출처) C로 쓴 자료구조론 2파, 이석호, 실리콘프레스 교보문고

 

1.3 알고리즘 명세

 

-알고리즘 정의) 특정한 일을 수행하는 명령어들의 유한 집합

- 외부에서 제공되는 데이터가 0개 이상 있어야 한다 (외부 입력 없이 실행되는 자체 프로그램도 알고리즘으로 인정된다는 의미)

-적어도 한 개의 결과를 생성해내야하며

-각 명령들은 명확하고 모호하지 않아야 한다.

-알고리즘의 명령대로 수행하면 어떤 경우에도 한정된 수의 단계 뒤에는 반드시 종료한다. (단계의 수는 한정되어있어야하며 무한 루프는 안 된다는 의미)

- 원칙적으로 모든 명령들은 종이와 연필만으로 수행될 수 있도록 기본적이어야함 (실행가능성의 충족이 필수적)

 

-알고리즘과 프로그램의 차이

: 단계의 수가 한정되어있어야 한다는 조건을 반드시 충족해야하는 여부에서 가장 큰 차이

:프로그램의 경우 반드시 종료해야하지 않아도 됨

:ex) OS- 시스템이 붕괴하기 이전에는 종료하지 않고 다른 작업이 입력될 때까지 계속 대기 루프를 돌고 있음

---

1.4 데이터 추상화

 

-데이터타입(data type)

: 객체(object)와 그 객체 위에 작동하는 연산(operation) 의 집합이다.

: 프로그램을 작성할 때 우리는 객체와 연산 두 가지 측면을 생각해보아야 함

: 연산은 언어로 정의가 되든 라이브러리로 정의되든 간에 그 이름, 매개변수, 그리고 결과가 명세되어야 한다.

:데이터 타입에 대한 연산에 대해 모두 알아야 할 뿐 아니라 데이타 타입의 객체가 어떻게 표현이 되는지도 알아야 함

: 데이터타입에 대한 객체의 표현 방법을 이해하는 것은 유용하면서도 위험

: 이러한 표현방법을 알면 알고리즘을 기술할 때 유용할 수도 있으나 개체의 표현을 변경시키고자 한다면 이것을 이용하는 루틴도 변경시켜야하기 때문이다.

+대부분의 소프트에어 설계자는 데이타 타입의 객체 표현에 대한 구체적인 내용을 사용자가 알지 않아도 되게 하는 것이 좋은 방법이라고 말함, 이 경우 사용자는 제공되는 함수를 통해 객체를 처리할 수 있음 (사용자가 그의 알고리즘을 다시 코딩할 필요가 없음을 의미)

 

-추상데이터타입(ADT, Abstract Data Type)

: 객체의 명세와 그 연산의 명세가 객체의 표현과 연산의 구현으로부터 분리된 데이타 타입

+명세) 분명하고 자세한 내용과 내역

: ADT 연산의 명세는 모든 함수의 이름, 그 함수의 매개변수 타입, 그리고 함수의 결과 타입으로 구성되며, 함수가 수행하는 기능에 대한 기술이 있어야 한다

:그러나 내부적인 표현이나 구현의 독립에 대한 자세한 설명은 필요가 없다 -> 구현에 독립적임

: 데이타 타입의 함수는 세 가지 범주 각각에 대해 적어도 하나씩의 함수를 포함

1)생성자/구성자. 지정된 타입에 맞는 새로운 인스턴스를 생성한다

2) 변환자. 일반적으로 1개 이상의 다른 인스턴스를 이용하여 지정된 타입의 한 인스턴스를 만든다.

3) 관찰자/보고자. 데이타타입의 인스턴스에 대한 정보를 제공하며, 인스턴스를 변경시키지 않는다.

 

-ADT 표기법

: ADT 정의는 그 ADT의 이름으로 시작하며 이 정의에는 두 부문, 객체와 함수가 있음

: 객체는 정의되었지만 그 표현에 대해서는 명확한 참조를 하지 않는다.

...

---

1.5 성능 분석

 

- 이 책의 목적 중 하나는 프로그램에 대한 평가 능력을 향상시키는 것에 있음 (자료구조와 알고리즘의 공부 이유도 여기에 있음)

 

-프로그램의 판단 기준

: 프로그램이 원래의 명세와 부합하는가?

: 정확하게 작동하는가?

: 프로그램을 어떻게 사용하고 어떻게 수행하는지에 관한 문서화가 프로그램 내에 되어져 있는가?

:논리적 단위를 생성하기 위해 프로그램이 함수를 효과적으로 사용하는가?

:프로그램의 코드의 가독성은 양호한가?

 

:프로그램의 메인 메모리와 보조기억장치를 효율적으로 사용하는가?

:작업에 대한 프로그램의 실행시간은 허용할만 한가?

       -> 이 두 기준은 성능 평가에 초점을 두고 있음 (성능분석의 복잡도이론, 성능측정)

 

-공간복잡도

: 프로그램의 공간 보갑도는 프로그램을 실행시켜 완료하는 데 필요로하는 공간의 양이다.

: 프로그램이 필요로하는 공간은 고정공간과 가변공간의 합이다

:고정공간요구. 프로그램의 입출력의 횟수나 크기와 관계 없는 공간 요구를 의미한다. 명령어 공간(코드 저장을 위한 공간), 단순 변수, 고정크기의 구조화변수(struct), 상수들을 위한 공간 등을 포함한다.

: 가변공간요구. 해결하려는 문제의 특정 인스턴스 I에 의존하는 크기를 가진 구조화 변수들을 위하여 공간이 구성되었다.인스턴스 I에 작업하는 프로그램 P의 가변공간 요구는 Sp(I)로 표기함, I와 관련된 입출력의 횟수, 크기, 값 등이 있을 수 있다.

:프로그램의 공간복잡도를 분석할 때에는 보통 가변공간요구에 대해서만 관심을 두며 이는 여러 프로그램의 공간 복잡도를 비교하려 할 때 유효하다.

 

-시간복잡도

: 프로그램을 실행시켜 완료하는데 필요한 컴퓨터 시간의 양을 의미한다.

: 프로그램 P에 소요되는 시간 T(P)는 컴파일시간과 실행시간을 합한 것

: 컴파일 시간은 인스턴스 특성에 의존하지 않기 때문에 고정공간요구와 비슷하며, 또한 프로그램이 일단 정확히 수행된다는 것이 검증이 되면, 프로그램을 다시 컴파일하지 않고도 여러번 수행할 수 있다.

: 실행시간을 결정하는 것은 컴파일러의 속성에 대한 상당한 지식이 요구되기 때문에 쉬운 작업이 아니며 컴파일러가 어떻게 원시 프로그램을 목적코드로 변환시키는지 알아야 한다.

: 실행시간에 대한 자세한 견적을 얻기 위해 노력을 할 필요는 없으며 만약 시간을 꼭 알아내야 한다면 가장 좋은 방법은 시스템 클럭을 이용하는 것

: 다른 방법은 프로그램이 수행하는 연산의 횟수를 계산하는 것이며 이것은 컴퓨터에 독립적인 견적이다

+ 요약

: 프로그램의 시간 복잡도는 그 프로그램의 기능을 수행하기 위해 프로그램이 취한 단계의 수로 표현이 된다.

:단계의 수는 그 자체가 인스턴스 특성을 갖는 함수이다.

 

 

-점근표기법