데이터 구조 와 알고리즘 총화 (1)

                                (1)

개발 도구 와 핵심 기술: 데이터 구조 와 알고리즘 요약 저자: 어젯밤 별 작성 시간: 2020 년 04 월 28 일 1. 데이터 구조의 개념: 데이터 구 조 는 서로 일정한 관 계 를 가 진 데이터 집합 을 말한다. 데이터 구 조 는 주로 논리 구조, 논리 구조의 연장 과 기본 알고리즘, 물리 구조, 연산 집합 을 연구한다.한편, 논리 구 조 는 세 가지 로 나 뉜 다. (1) 선형 구조: 구조 중의 데이터 요소 간 에 일대일 의 선형 관계 가 존재 하고 첫 번 째 와 마지막 데이터 요 소 를 제외 하고 모든 요 소 는 하나의 전구 와 하나의 원숭이 급 데이터 요소 만 있다.(2) 트 리 구조: 구조 중의 데이터 요소 사이 에 한 쌍 의 다 차원 관계 가 존재 한다. 뿌리 노드 를 제외 하고 모든 데이터 요 소 는 하나의 전구 요소 만 있 고 0 개 또는 몇 개의 후계 데이터 요소 만 있 을 수 있다.(3) 그림 구조: 구조 중의 요소 간 에 여러 쌍 의 관계 가 존재 하고 모든 데이터 요 소 는 0 개 또는 몇 개의 전구 데이터 요소 와 0 개 또는 몇 개의 후계 요소 가 있 을 수 있다.데이터 구조의 세 가지 주요 구성 부분;1. 논리 구조: 데이터 간 의 논리 적 관계 에 대한 설명.2. 저장 구조: 데이터 요소 가 컴퓨터 에서 의 저장 과 논리 관계 의 표현 을 데이터 의 저장 구조 또는 물리 구조 라 고 한다.3. 데이터 조작: 데 이 터 를 연산 합 니 다.4. 데이터 형식: 하나의 값 의 집합 과 이 값 집합 에 정 의 된 작업 의 총칭 을 말한다.데이터 형식 은 데이터 구조 와 밀접 한 관 계 를 가 진 개념 이다.C 언어 에서 데이터 유형 은 기본 유형 과 구조 유형 이 있다.5. 데이터 구 조 는 데이터 형식 과 다 르 고 데이터 대상 과 다르다. 이 는 데이터 형식의 데이터 대상 을 묘사 할 뿐만 아니 라 데이터 대상 각 요소 간 의 상호 관 계 를 묘사 해 야 한다.2. 알고리즘 의 개념 과 특징 (1) 데이터 구조 에서 가장 중요 한 구성원 - 알고리즘: 알고리즘 은 문 제 를 해결 하 는 방법 이 고 프로그램 디자인 의 정수 이 며 프로그램 디자인 의 실질 은 바로 문 제 를 해결 하 는 알고리즘 을 구성 하 는 것 이다.알고리즘 의 디자인 은 데이터 의 논리 구조 에 달 려 있 고 알고리즘 의 실현 은 데이터 의 물리 적 저장 구조 에 달 려 있다.알고리즘 의 개념 과 특성: 알고리즘 은 특정한 문제 에 대한 풀이 절차 에 대한 설명 으로 명령 의 유한 한 서열 이다.(2) 하나의 알고리즘 에는 다섯 가지 중요 한 특징 이 있어 야 한다. 1. 가난 성 이 있다. 하나의 알고리즘 은 유한 한 조작 절 차 를 포함해 야 한다.즉, 하나의 알고리즘 은 몇 가지 절 차 를 실행 한 후에 끝 낼 수 있 고 모든 단 계 는 제 한 된 시간 안에 완성 할 수 있어 야 한다.2. 확정 성: 알고리즘 중의 모든 단 계 는 정확 한 의 미 를 가 져 야 하고 이의 성 을 가 져 서 는 안 된다.3. 타당 성: 알고리즘 중의 모든 절 차 는 효과적으로 집행 되 고 확 정 된 결 과 를 얻 을 수 있어 야 한다.4. 입력: 입력 이란 알고리즘 이 실 행 될 때 외부 에서 필요 한 데 이 터 를 얻 는 것 을 말한다.컴퓨터 가 프로그램 을 실행 하 는 목적 은 데이터 처 리 를 하기 위해 서 이다. 대부분의 경우 이 데 이 터 는 입력 을 통 해 얻어 야 한다.어떤 경우 에 데 이 터 는 알고리즘 에 포함 되 어 있 고 알고리즘 이 실 행 될 때 데이터 가 필요 하지 않 기 때문에 하나의 알고리즘 은 0 개 이상 의 입력 을 할 수 있 습 니 다.5. 출력: 하나의 알고리즘 이 하나 이상 의 출력 이 있 는데 이것 은 알고리즘 이 데이터 처 리 를 한 결과 입 니 다.출력 이 없 는 알고리즘 은 무의미 하 다.(3) 알고리즘 디자인 의 요구: 알고리즘 디자인 의 좋 고 나 쁨 은 프로그램의 집행 효율 과 관련 되 고 알고리즘 의 디자인 은 다음 과 같은 네 가지 요 구 를 만족 시 켜 야 한다. 1. 정확성: 정확 한 의 미 는 알고리즘 이 모든 합 법 적 인 입력 데이터 에 대해 요 구 를 만족 시 키 는 결 과 를 얻 을 수 있다 는 것 이다. 사실은 알고리즘 의 정확성 을 검증 하 는 것 이 매우 어렵다.통상 적 으로 합 법 적 인 입력 데이터 의 양 이 너무 많 기 때문에 궁 거 법 으로 일일이 검증 하 는 것 은 비현실적이다.알고리즘 의 정확성 이란 알고리즘 이 테스트 요구 에 도달 했다 는 것 을 말한다.2. 가 독성: 알고리즘 의 가 독성 이란 사람 이 알고리즘 읽 기 이해 의 난이도, 가 독성 이 높 은 알고리즘 이 교류 하기 쉽 고 알고리즘 의 디 버 깅 과 수정 에 유리 하 다 는 것 을 말한다.일반적으로 알고리즘 의 가 독성 을 증가 시 키 는 것 은 알고리즘 을 쓸 때 들 여 쓰기 형식 에 따라 쓰기, 모듈 별로 쓰기 등 방법 으로 알고리즘 의 가 독성 을 증가 시 킬 수 있다.3. 건장 성: 불법 입력 데이터 에 대해 알고리즘 은 예측 할 수 없 는 결 과 를 초래 하 는 것 이 아니 라 해당 하 는 응답 을 할 수 있 습 니 다.4. 효율 과 저 저장량 의 수요: 효율 은 알고리즘 의 집행 시간 을 말한다.같은 문 제 를 해결 하 는 여러 알고리즘 에 대해 실행 시간 이 짧 은 알고리즘 은 효율 이 높다.저장량 수 요 는 알고리즘 실행 과정 에서 필요 한 최대 저장 공간 을 말한다.저장량 수요 가 적은 알고리즘 일수 록 효율 이 높다.(4) 알고리즘 에 대한 분석 은 한 문 제 를 해결 하 는 데 여러 가지 알고리즘 이 있 을 수 있다. 그러면 그들의 우열 을 어떻게 판단 해 야 하 는 기준 이 매우 많 지만 한 알고리즘 의 정확성 은 반드시 보장 해 야 한다. 주요 한 지 표 는 그의 효율 이다.1. 알고리즘 의 효율 적 인 도량: 알고리즘 이 실행 되 는 시간 은 해당 하 는 프로그램 이 컴퓨터 에서 실행 하 는 데 소모 되 는 시간 이다.프로그램 이 컴퓨터 에서 실행 하 는 데 소요 되 는 시간 은 다음 과 같은 요소 와 관련 이 있 습 니 다. 알고리즘 자체 가 선택 한 전략 입 니 다.② 쓰기 프로그램의 언어;③ 컴 파일 된 코드 품질;④ 기계 가 명령 을 수행 하 는 속도;⑤ 문제 의 규모.① 조 는 알고리즘 의 좋 고 나 쁨 의 근본 이 고 ② ③ 조 는 구체 적 인 소프트웨어 지원 을 보고 ④ 조 는 하드웨어 의 성능 을 봐 야 한다.하나의 알고리즘 을 측정 하 는 효율 은 구체 적 인 기계 의 소프트, 하드웨어 환경 을 버 리 고 프로그램의 언어, 컴 파일 로 인해 발생 하 는 기계 코드 품질, 기계 가 명령 을 집행 하 는 속 도 는 모두 소프트 하드웨어 환경 에 속한다.그래서 컴퓨터 소프트 하드웨어 와 관련 된 요 소 를 떠 나 한 프로그램의 운행 시간 은 알고리즘 의 좋 고 나 쁨 과 문제 의 규모 에 만 의존한다.특정한 알고리즘 에 대해 알고리즘 자체 의 효율 만 고려 하고 알고리즘 자체 의 집행 효율 은 문제 규모 의 함수 이다.같은 문제 에 대해 서로 다른 전략 을 선택 하면 서로 다른 알고리즘 에 대응 하고 서로 다른 알고리즘 은 각자 의 문제 규모 함수 에 대응 하 며 이런 함수 에 따라 알고리즘 의 우열 을 비교 할 수 있다.알고리즘 의 효율 은 시간 과 공간 두 가지 측면 을 포함 하 는데 각각 시간 복잡 도와 공간 복잡 도 라 고 부른다.2. 알고리즘 의 시간 복잡 도: 한 알고리즘 의 집행 시간 은 대체적으로 모든 문장의 집행 시간의 총화 와 같 고 문장의 집행 시간 은 이 문장의 집행 횟수 와 한 번 의 집행 에 필요 한 시간의 곱 을 말한다.문 구 를 한 번 실행 하 는 데 필요 한 구체 적 인 시간 은 기계 의 속도, 컴 파일 러 의 질, 입력 데이터 등 과 밀접 한 관 계 를 가지 고 알고리즘 디자인 의 좋 고 나 쁨 과 무관 하 다.따라서 알고리즘 중의 문장의 실행 횟수 로 알고리즘 의 효율 을 측정 할 수 있다.알고리즘 의 시간 복잡 도, 기록: T (n) = O (f (n).3. 알고리즘 의 공간 복잡 도: 공간 복잡 도 를 알고리즘 에 필요 한 양 으로 하고 S (n) = O (f (n) 로 기록 하 며 그 중에서 n 은 문제 의 규모 이다.프로그램 이 실 행 될 때 자체 에 사용 되 는 명령, 상수, 변수 와 입력 데 이 터 를 저장 해 야 하 는 것 외 에 데 이 터 를 조작 하 는 보조 저장 공간 도 필요 하 다.그 중에서 입력 데이터 가 차지 하 는 구체 적 인 저장량 은 문제 자체 에 만 달 려 있 고 알고리즘 과 무관 하 므 로 이 알고리즘 이 실현 할 때 필요 한 보조 공간 단원 수 를 분석 하면 된다.알고리즘 의 집행 시간 과 저장 공간의 소 모 는 모순 체 이다. 즉, 알고리즘 이 집행 하 는 효율 은 보통 저장 공간 을 늘 리 는 대가 로 하 는 것 이 고 반대로 도 마찬가지 이다.그러나 일반적인 상황 에서 볼 때 알고리즘 집행 시간 을 알고리즘 우열 의 주요 평가 기준 으로 한다.4. 데이터 구조의 저장 방식: 데이터 구조 가 컴퓨터 메모리 에 저장 되 는 것 은 데이터 요소 의 저장 과 요소 간 의 관 계 를 나타 낸다.요소 간 의 관 계 는 컴퓨터 에서 두 가지 서로 다른 표현 방법 이 있다. 순서 표시 와 비 순서 표시 이다.이 를 통 해 두 가지 서로 다른 저장 구 조 를 얻 을 수 있다. 순서 저장 구조 와 체인 저장 구조 이다.순서 저장 구조: 데이터 요소 가 메모리 에 있 는 상대 적 인 위치 로 데이터 요소 간 의 논리 구조 (관계) 를 나타 낸다.체인 저장 구조: 모든 데이터 요소 에 다른 요소 의 주 소 를 저장 하 는 지침 을 추가 하고 이 지침 으로 데이터 요소 간 의 논리 구조 (관계) 를 표시 합 니 다.순서 구조: 데이터 요소 가 저 장 된 주 소 는 연속 적 입 니 다.체인 구조: 데이터 요소 가 저 장 된 주 소 는 연속 을 요구 하지 않 습 니 다.데이터 의 논리 구조 와 물리 구 조 는 밀접 한 두 가지 측면 이다. 하나의 알고리즘 의 디자인 은 선택 한 논리 구조 에 달 려 있 고 알고리즘 의 실현 은 사용 하 는 저장 구조 에 의존한다.