2019 왕도 '데이터 구조' - 서론

데이터 구조의 기본 개념
1. 기본 개념 과 용어
   1. 데이터: 정보의 매개체 로 객관 적 인 사물 의 속성 을 묘사 하 는 수, 문자 와 컴퓨터 에 입력 되 고 컴퓨터 프로그램 에 의 해 식별 되 고 처리 되 는 모든 기호의 집합 이다.
   2. 데이터 요소: 데이터 요 소 는 데이터 의 기본 단위 로 서 전체적인 고려 와 처 리 를 한다.하나의 데이터 요 소 는 몇 개의 데이터 항목 으로 구성 할 수 있 고 데이터 항목 은 데이터 요 소 를 분할 할 수 없 는 최소 단위 이다.예 를 들 어 학생 기록 은 하나의 데이터 요소 로 학 번, 성명, 성별 등 데이터 항목 으로 구성 된다.
  3. 데이터 대상: 데이터 대상 은 같은 성질 을 가 진 데이터 요소 의 집합 이 고 데이터 의 서브 집합 이다.예 를 들 어 정수 데이터 대상 은 집합 N = {0, + - 1, + - 2,...}
   4. 데이터 형식: 데이터 형식 은 하나의 값 의 집합 과 이 집합 에서 이전 작업 의 총칭 입 니 다.
   5、 추상 적 인 데이터 형식 (ADT) 은 데이터 모델 과 이 모델 에 정 의 된 작업 을 말한다.추상 적 인 데이터 유형의 정 의 는 그의 논리 적 특성 에 만 달 려 있 고 컴퓨터 내부 에서 어떻게 표현 하고 실현 하 는 지 와 무관 하 다. 즉, 내부 구조 가 어떻게 변화 하 든 그의 수학 적 특성 이 변 하지 않 으 면 외부 사용 에 영향 을 주지 않 는 다.일반적으로 (데이터 대상, 데이터 관계, 기본 조작 집합) 과 같은 3 원 그룹 으로 추상 적 인 데이터 형식 을 나타 낸다.
   6. 데이터 구조: 모든 문제 에서 데이터 요 소 는 고립 된 존재 가 아니 라 그들 사이 에 특정한 관계 가 존재 하 는데 이런 데이터 요소 가 서로 간 의 관 계 를 구조 라 고 부른다.데이터 구 조 는 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합 이다.데이터 구 조 는 세 가지 내용 을 포함한다. 논리 구조, 저장 구조 와 데이터 의 연산 이다.데이터 의 논리 구조 와 저장 구 조 는 밀접 하여 구분 할 수 없 는 두 가지 측면 이다. 한 알고리즘 의 디자인 은 선택 한 논리 구조 에 달 려 있 고 알고리즘 의 실현 은 사용 하 는 저장 구조 에 의존한다.
 2. 데이터 구조의 세 가지 요소
   1. 데이터 의 논리 적 요소
     논리 구 조 는 데이터 요소 간 의 논리 적 관 계 를 말한다. 즉, 논리 적 관계 에서 데 이 터 를 묘사 하 는 것 이다.그것 은 데이터 의 저장 과 상 관 없 이 컴퓨터 에 독립 되 어 있다.데이터 의 논리 구 조 는 선형 구조 와 비 선형 구조 로 나 뉘 는데 선형 표 는 전형 적 인 선형 구조 이다.집합, 나무 와 그림 은 전형 적 인 비 선형 구조 이다.
     집합: 구조 중의 요소 간 에는 '같은 집합 에 속 하 는' 관 계 를 제외 하고 다른 관계 가 없다.
     선형 구조: 구조 중의 요 소 는 일대일 의 관계 만 존재 한다.
     트 리 구조: 구조 중의 데이터 요소 사이 에 한 쌍 이상 의 관계 가 존재 합 니 다.
     도형 이나 그물 모양 구조: 구조 중의 데 이 터 는 여러 쌍 의 관계 가 존재 한다.
   2. 데이터 의 저장 구조
     데이터 의 저장 구 조 는 데이터 구조 가 컴퓨터 에서 의 표현 (이미지 라 고도 함) 을 말 하 며 물리 구조 라 고도 부른다.그것 은 데이터 요소 의 표시 와 관계 의 표 시 를 포함한다.데이터 의 저장 구 조 는 논리 구조 가 컴퓨터 언어 로 이 루어 지 는 것 으로 계산 언어 에 의존한다.데이터 의 저장 구 조 는 주로 순서 저장, 체인 저장, 색인 저장, 해시 저장 등 이 있다.
    1) 순서 저장: 논리 적 으로 인접 한 요 소 를 물리 적 위치 에서 도 인접 한 저장 장치 에 저장 하고 요소 간 의 관 계 는 저장 장치 의 인접 관계 에 의 해 나타난다.그 장점 은 무 작위 접근 을 실현 할 수 있 고 모든 요소 가 가장 적은 저장 공간 을 차지 하 는 것 이다.단점 은 인접 한 전체 저장 장치 만 사용 할 수 있 기 때문에 외부 파편 이 많이 생 길 수 있다 는 것 이다.
    2) 링크 저장 소: 논리 적 으로 인접 한 요소 가 물리 적 위치 에서 도 인접 하도록 요구 하지 않 고 지시 요소 의 주 소 를 저장 하 는 지침 을 통 해 요소 간 의 논리 관 계 를 나타 낸다.파편 현상 이 나타 나 지 않 고 모든 저장 부 를 충분히 이용 하 는 것 이 장점 이다.단점 은 모든 요소 가 메모리 포인터 로 인해 추가 저장 공간 을 차지 하고 순서 액세스 만 가능 하 다 는 것 이다.
    3) 색인 저장: 요소 정 보 를 저장 하 는 동시에 추가 색인 표를 만 듭 니 다.색인 표 의 모든 항목 을 색인 항목 이 라 고 하 는데 색인 항목 의 일반적인 형식 은: (키워드, 주소) 입 니 다.검색 속도 가 빠르다 는 것 이 장점 이다.추가 색인 표를 추가 하면 저장 공간 을 많이 차지 하 는 것 이 단점 이다.또 데 이 터 를 추가 하거나 삭제 할 때 색인 표를 수정 해 야 하기 때문에 시간 이 많이 걸린다.
    4) 해시 저장 소: 원소 의 키워드 에 따라 칼슘 원소 의 저장 주 소 를 직접 계산 하여 Hash 저장 이 라 고도 부른다.그 장점 은 검색, 증가, 삭제 노드 의 조작 이 빠르다 는 것 이다.단점 은 해시 함수 가 좋 지 않 으 면 요소 저장 장치 의 충돌 이 발생 할 수 있 고 충돌 을 해결 하면 시간 과 공간 비용 이 증가 할 수 있다 는 것 이다.
  3. 데이터 의 연산
   데이터 에 가해 지 는 연산 은 연산 의 정의 와 실현 을 포함한다.연산 의 정 의 는 논리 구 조 를 대상 으로 연산 의 기능 을 지적 하 는 것 이다.연산 의 실현 은 저장 구 조 를 대상 으로 연산 의 구체 적 인 조작 절 차 를 지적 하 는 것 이다.
    4. 순환 대기 열 은 순서 표 로 표 시 된 대기 열 로 데이터 구조 입 니 다.스 택 은 추상 적 인 데이터 형식 으로 순서대로 저장 하거나 체인 으로 저장 할 수 있 으 며 논리 구조 만 표시 할 수 있 습 니 다.
3. 알고리즘 과 알고리즘 에 대한 평가
1. 알고리즘 의 기본 개념
알고리즘 은 특정한 문제 에 대한 풀이 절차 에 대한 설명 으로 명령 의 유한 한 서열 로 그 중에서 모든 명령 은 하나 이상 의 조작 을 나타 낸다.그 밖 에 하나의 알고리즘 은 5 가지 중요 한 특성 을 가지 고 있 습 니 다.2) 확정 알고리즘 중의 모든 명령 은 반드시 정확 한 의 미 를 가 져 야 하고 독자 가 이해 할 때 이의 성 이 생기 지 않 는 다.같은 입력 에 대해 서 는 같은 출력 만 얻 을 수 있다 는 것 이다.3) 타당 성 있 는 알고리즘 은 실행 가능 하 다. 즉, 알고리즘 에서 설명 한 조작 은 모두 이미 실 현 된 기본 연산 을 통 해 유한 한 번 에 실 현 될 수 있다.4) 하나의 알고리즘 을 입력 하면 하나 이상 의 입력 이 있 는데 이런 입력 은 특정한 대상 의 집합 에서 나온다.5) 하나의 알고리즘 을 출력 하 는 데 하나 이상 의 출력 이 있 는데 이런 출력 은 입력 과 특정한 관 계 를 가 진 양 이다.좋 은 알고리즘 을 설계 하려 면 다음 과 같은 목 표를 고려 해 야 한다.  1) 정확성 알고리즘 은 문 제 를 정확하게 해결 할 수 있어 야 한다.2) 가 독성 알고리즘 은 좋 은 가 독성 을 가지 고 사람들 이 이해 하 는 데 도움 이 되 어야 한다. 3) 건장 성 은 불법 데 이 터 를 입력 할 때 알고리즘 도 알 수 없 는 출력 결과 가 발생 하지 않도록 적절하게 반응 하거나 처리 할 수 있다.4) 효율 과 저 저장량 수요: 효율 은 알고리즘 이 실행 하 는 시간 을 말 하 는데 저장량 수 요 는 알고리즘 이 실행 하 는 과정 에서 필요 한 최대 저장 공간 을 말 하 는데 이 두 가 지 는 모두 문제 의 규모 와 관련된다.
2. 알고리즘 효율 의 도량
   시간 복잡 도와 공간 복잡 도 를 사용 하여 설명 합 니 다.
    1) 시간 복잡 도
        한 문장의 빈 도 는 이 문장 이 알고리즘 에서 반복 되 는 횟수 를 가리킨다.알고리즘 에서 모든 문장의 빈도 와 T (n) 로 기록 합 니 다. 이 알고리즘 은 문제 규모 n 의 함수 이 고 시간 복잡 도 는 주로 T (n) 의 수량 급 을 분석 합 니 다.알고리즘 중의 기본 연산 (최 심층 순환 내의 문장) 의 빈도 와 T (n) 의 동 수량 급 이기 때문에 보통 알고리즘 중의 기본 연산 의 빈도 f (n) 를 이용 하여 알고리즘 의 시간 복잡 도 를 분석한다.따라서 알고리즘 의 시간 복잡 도 는 다음 과 같다.
                                                             T(n) = O(f(n))
       f (n) 에서 n 에 따라 가장 빨리 증가 하 는 항목 을 취하 여 그 계 수 를 1 로 시간 복잡 도의 도량 으로 한다.
      'O' 의 의 미 는 T (n) 의 수량 급 이다. 그 엄격 한 수학 정 의 는 T (n) 와 f (n) 는 정수 집합 에 정 의 된 두 함수 로 정상 수 C 와 n0 이 존재 한다. n > = n0 시 0 < = T (n) < = C * f (n) 를 만족 시 킵 니 다.
      알고리즘 의 시간 복잡 도 는 문제 의 규모 n 뿐만 아니 라 입력 대기 데이터 의 성질 (예 를 들 어 입력 데이터 의 초기 상태) 에 도 달 려 있다.
       예 를 들 어 배열 A [0... n - 1] 에서 주어진 값 k 를 찾 는 알고리즘 은 대체적으로 다음 과 같다.

i=n-1;
while(i>=0 && (A[i] != k))
   i--;
return i;

      이 알고리즘 문장의 문장 (3) (기본 연산) 의 주파 수 는 문제 규모 n 과 관련 이 있 을 뿐만 아니 라 입력 실례 중의 A 의 각 요소 의 수치 와 k 의 수치 와 도 관련 이 있다.
          1) A 에 k 와 같은 요소 가 없 으 면 문장 (3) 의 빈 도 는 f (n) = n 이다.
          2)  만약 에 A 의 마지막 요소 가 k 와 같다 면 문장 (3) 의 빈도 f (n) 는 상수 0 이다.
      최 악의 시간 복잡 도 는 최 악의 상황 에서 알고리즘 의 시간 복잡 도 를 말한다.
      평균 시간 복잡 도 는 모든 입력 실례 가 등 확률 로 나타 날 수 있 는 상황 에서 알고리즘 의 기대 운행 시간 을 가리킨다.
      가장 좋 은 시간 복잡 도 는 가장 좋 은 상황 에서 알고리즘 의 시간 복잡 도 를 말한다.
      일반적으로 최 악의 상황 에서 의 시간 복잡 도 를 고려 하여 알고리즘 의 운행 시간 이 그것 보다 더 길 지 않도록 한다.
     한 프로그램의 복잡성 을 분석 할 때 다음 과 같은 두 가지 규칙 이 있다.
         a) 덧셈 규칙
          T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n),g(n)))  
         b) 곱셈 규칙
          T(n) = T1(n)*T2(n) = O(f(n))*O(g(n)) = O(f(n) * g(n))
     흔히 볼 수 있 는 점진 적 복잡 도 는 다음 과 같다.
      O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) O(n^3) < O(2^n) < O(n!) < O(n^n)
   2) 공간 복잡 도
     알고리즘 의 공간 복잡 도 S (n) 는 이 알고리즘 이 소모 하 는 저장 공간 으로 정의 되 며 문제 규모 n 의 함수 입 니 다.점진 적 인 공간 복잡 도 는 흔히 공간 복잡 도 라 고 부 르 는데 S (n) = O (g (n) 로 기록한다.
     하나의 컴퓨터 프로그램 은 자체 가 사용 하 는 명령, 상수, 변수 와 입력 데 이 터 를 저장 하 는 공간 이 필요 할 뿐만 아니 라 데 이 터 를 조작 하 는 작업 단원 과 계산 에 필요 한 정 보 를 저장 하 는 보조 공간 도 필요 하 다. 만약 에 입력 데이터 가 차지 하 는 공간 이 문제 자체 에 만 달 려 있 고 알고리즘 과 무관 하 다 면 입력 과 프로그램 을 제외 한 추가 공간 만 분석 해 야 한다.
      알고리즘 제자리 작업 이란 알고리즘 에 필요 한 보조 공간 이 상수, 즉 O (1) 를 말한다.