데이터 구조 기본 개념 및 복잡 도 분석

다음 내용 은 인터넷 에서 정리 하여 개인 학습 에 만 사용 합 니 다.
1. 데이터 구조 기본 개념
데이터 구조의 세 가지 요소:

데이터 의 논리 구조: 논리 구 조 는 데이터 요소 간 의 논리 적 관 계 를 말한다. 즉, 논리 적 관계 에서 데 이 터 를 묘사 하 는 것 이다.데이터 의 구체 적 인 저장 과 는 무관 하 다.데이터 의 논리 구 조 는 선형 구조 와 비 선형 구조 로 나 뉘 는데 선형 표 는 전형 적 인 선형 구조 이다.집합, 나무 와 그림 은 전형 적 인 비 선형 구조 이다.

데이터 의 저장 구조: 저장 구 조 는 데이터 구조 가 컴퓨터 에서 나타 나 는 것 을 말 하 며 물리 구조 라 고도 부른다.데이터 요소 의 표시 와 관 계 를 포함 한 표시.데이터 의 저장 구 조 는 주로 순서 저장, 체인 저장, 색인 저장 과 해시 저장 이 있다.

순서 저장: 논리 적 으로 인접 한 요 소 를 물리 적 위치 에서 도 인접 한 저장 장치 에 저장 하고 요소 간 의 관 계 는 저장 장치 의 인접 관계 에 의 해 나타난다.장점 은 무 작위 접근 을 실현 할 수 있 고 모든 요소 가 가장 적은 저장 공간 을 차지 하 는 것 이다.단점 은 인접 한 저장 장치 하나만 사용 할 수 있 기 때문에 외부 파편 이 많이 생 길 수 있다 는 것 이다.

링크 저장: 논리 적 으로 인접 한 요소 가 물리 적 위치 에서 도 인접 하도록 요구 하지 않 고 지시 요소 저장 주소 의 지침 을 통 해 요소 간 의 논리 관 계 를 나타 낸다.파편 현상 이 나타 나 지 않 고 모든 저장 부 를 충분히 이용 하 는 것 이 장점 이다.단점 은 모든 요소 간 에 포인터 저장 으로 인해 추가 공간 을 차지 하고 순서대로 만 읽 을 수 있다 는 것 이다.

색인 저장: 요소 정 보 를 저장 하 는 동시에 추가 색인 표를 만 듭 니 다.색인 표 의 모든 항목 을 색인 항목 이 라 고 하 는데 색인 항목 의 일반적인 형식 은 다음 과 같다. (키워드, 주소)검색 속도 가 빠르다 는 것 이 장점 이다.추가 색인 표를 추가 하면 저장 공간 을 많이 차지 하 는 것 이 단점 이다.또 데 이 터 를 추가 하고 삭제 할 때 색인 표를 수정 해 야 하기 때문에 시간 이 많이 걸린다.

해시 저장: 요소 의 키워드 에 따라 이 요소 의 저장 주 소 를 직접 계산 하고 Hash 저장 이 라 고도 부른다.그 장점 은 검색, 증가, 삭제 노드 의 조작 이 빠르다 는 것 이다.단점 은 해시 함수 가 좋 지 않 으 면 요소 저장 장치 의 충돌 이 발생 할 수 있 고 충돌 을 해결 하 는 데 시간 이 증가 할 수 있다 는 것 이다.

데이터 의 연산: 데이터 에 가해 진 연산 은 연산 의 정의 와 실현 을 포함한다.연산 의 정 의 는 논리 구 조 를 대상 으로 연산 의 기능 을 지적 하 는 것 이다.연산 의 실현 은 저장 구 조 를 대상 으로 연산 의 구체 적 인 조작 절 차 를 지적 하 는 것 이다.

2. 복잡 도 분석
2.1 알고리즘
알고리즘 은 특정한 문제 에 대한 풀이 절차 에 대한 설명 으로 명령 의 유한 한 서열 로 그 중에서 모든 명령 은 하나 이상 의 조작 을 나타 낸다.그 밖 에 알고리즘 은 다음 과 같은 5 가지 중요 한 특성 을 가지 고 있다.

가난 성 이 있 습 니 다. 하나의 알고리즘 은 항상 (합 리 적 인 입력 값 에 대해) 실행 이 끝 난 후에 끝나 야 하고 모든 단 계 는 가난 한 시간 안에 완성 할 수 있 습 니 다.

확정 성: 알고리즘 의 모든 지령 은 반드시 정확 한 의 미 를 가 져 야 하고 독자 가 이해 할 때 이의 성 이 생기 지 않 는 다.같은 입력 에 대해 서 는 같은 출력 만 나 올 수 있다 는 것 이다.

타당 성: 하나의 알고리즘 은 실행 가능 하 다. 즉, 알고리즘 중의 설명 작업 은 모두 이미 실 현 된 기본 연산 집행 유한 회 를 통 해 이 루어 질 수 있다.

입력: 하나의 알고리즘 은 0 개 또는 여러 개의 입력 이 있 는데 이런 입력 은 특정한 대상 의 집합 에서 나온다.

출력: 하나의 알고리즘 은 하나 이상 의 출력 이 있 는데 이런 출력 은 입력 과 특정한 관 계 를 가 진 양 입 니 다.

2.2 시간 복잡 도
알고리즘 에서 모든 문 구 를 반복 적 으로 실행 하 는 횟수 의 합 을 T (n) 로 기록 하고 시간 복잡 도 는 주로 T (n) 의 수량 급 을 분석 합 니 다.O (f (n) 로 기록 하 다.f (n) = an3 + bn2 + c * n 을 가정 하면 O (f (n) = O (n ^ 3) 는 예 를 들 어 배열 A [0 · n - 1] 에서 값 K 위 치 를 찾 아야 한다 고 가정 하면 알고리즘 은 대체적으로 다음 과 같다.

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

이 알고리즘 의 복잡 도 는 문제 규모 n 과 관련 이 있 을 뿐만 아니 라 입력 인 스 턴 스 에서 A 의 각 요소 의 수치 와 K 의 수치 와 도 관련 이 있 습 니 다.

A 에 K 와 같은 요소 가 없 으 면 두 번 째 줄 코드 의 실행 횟수 는 f (n) = n

이다.

A 의 마지막 요소 가 K 와 같 으 면 두 번 째 줄 에서 실행 하 는 횟수 는 f (n) = 0 이다.

최 악의 시간 복잡 도: 최 악의 상황 에서 알고리즘 의 시간 복잡 도 를 말한다.

가장 좋 은 시간 복잡 도: 가장 좋 은 상황 에서 알고리즘 의 시간 복잡 도 를 말한다.

평균 시간 복잡 도: 모든 입력 실례 등 확률 이 발생 할 수 있 는 상황 에서 알고리즘 의 기대 운행 시간 을 말한다.

일반적으로 최 악의 상황 에서 의 시간 복잡 도 를 고려 하여 알고리즘 의 운행 시간 이 그것 보다 더 길 지 않도록 한다.알고리즘 의 복잡 도 를 분석 할 때 다음 과 같은 두 가지 규칙 이 있다.

덧셈 규칙: O (f (n) + O (g (n)) = O (max (f (n), g (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.3 공간 복잡 도
공간 복잡 도 는 알고리즘 에 소모 되 는 저장 공간 입 니 다. 자체 에 사용 되 는 명령, 상수, 변수 와 입력 데 이 터 를 저장 하 는 동시에 데 이 터 를 조작 하 는 작업 단원 과 보조 공간 이 필요 합 니 다. 그 는 문제 규모 n 의 함수 입 니 다. 알고리즘 제자리 작업: 계산법 에 필요 한 보조 공간 은 상수, 즉 O (1) 를 말 합 니 다.