데이터 구조 와 알고리즘 기초 개술 입문 필수!

1. 데이터 의 논리 구조 (1) 집합 구조 중의 데이터 요소 간 에는 같은 집합 에 속 하 는 관 계 를 제외 하고 그 어떠한 관계 도 없다.
(2) 선형 구조 중의 데이터 요소 사이 에 일대일 의 선형 관계 가 존재 한다.
(3) 트 리 구조 중의 데이터 요소 사이 에 한 쌍 의 다 차원 관계 가 존재 한다.
(4) 도형 구조 중의 데이터 요소 사이 에 여러 쌍 의 임 의적 인 관계 가 존재 한다.
2. 데이터 의 저장 구조 (1) 순서 이미지 - > 순서 저장 은 그 중의 상대 적 인 위 치 를 통 해 데이터 요소 간 의 논리 적 관 계 를 나타 낸다 (배열 과 비슷 하 다).
(2) 비 순차 이미지 - > 체인 저장 소 는 포인터 로 데이터 요소 간 의 논리 적 관 계 를 나타 낸다 (링크 와 비슷 하 다)

             ：                    ，        ，            。

3. 알고리즘 의 개념

     +  =  

1. 빈곤 성 이 있 으 면 임의의 그룹의 합 법 적 인 입력 값 에 대해 가난 한 절 차 를 실행 한 후에 반드시 끝 낼 수 있다. 즉, 알고리즘 중의 모든 절 차 는 제 한 된 시간 안에 완성 할 수 있다.
2. 확정 알고리즘 의 모든 단 계 는 정확 한 정 의 를 내 려 야 합 니 다. 알고리즘 의 집행 자 나 읽 는 사람 이 그 의미 와 어떻게 집행 하 는 지 를 명 확 히 할 수 있 고 그 어떠한 조건 에서 도 알고리즘 은 하나의 실행 경로 만 있 습 니 다.
3. 타당 성 알고리즘 은 실행 가능 해 야 한다. 알고리즘 중의 모든 조작 은 반드시 기본 적 이 어야 하고 이미 실 현 된 기본 조작 연산 을 통 해 유한 하 게 실현 할 수 있다.
4. 하나의 알고리즘 을 입력 할 때 0 개 이상 의 입력 이 있어 야 합 니 다. 그들 은 알고리즘 에 필요 한 제 습 량 이나 가공 대상 의 표시 입 니 다.일부 입력 량 은 알고리즘 실행 과정 에서 입력 해 야 하 며, 어떤 알고리즘 은 표면 에 입력 하지 않 아 도 되 며, 실제로는 알고리즘 에 포함 되 어 있다.
5. 출력 알고리즘 이 있 으 면 하나 이상 의 출력 이 있어 야 합 니 다. 이것 은 입력 과 확실한 관 계 를 가 진 양 적 값 이 고 알고리즘 이 정보 가공 을 한 결과 입 니 다. 이러한 확정 관 계 는 바로 알고리즘 의 기능 입 니 다.
4. 알고리즘 의 평가 기준 1. 정확성 정확성 이란 알고리즘 이 구체 적 인 문제 의 요 구 를 만족 시 킬 수 있다 는 것 을 말한다. 즉, 모든 합 법 적 인 입력 에 대해 알고리즘 은 정확 한 결 과 를 얻 을 수 있다.
2. 가 독성 가 독성 이란 알고리즘 이 이해 되 는 난이도 이다.알고리즘 은 주로 사람 을 위해 읽 고 교류 하 는 것 이 고 그 다음은 컴퓨터 를 위해 실행 하 는 것 이기 때문에 알고리즘 은 사람들의 이해 가 더욱 쉬 워 야 한다.다른 한편, 읽 기 어 려 운 프로그램 은 많은 오 류 를 숨 기기 쉽 고 디 버 깅 하기 어렵다.
3. 건장 성, 건장 성 은 노 봉 성, 즉 불법 입력 에 대한 저항력 이 라 고도 부른다.입력 데이터 가 불법 일 때 알고리즘 은 이상 한 출력 결과 가 나 오 는 것 이 아니 라 적절하게 반응 하거나 상응하는 처 리 를 해 야 한다.또한 오 류 를 처리 하 는 방법 은 프로그램의 실행 을 중단 하 는 것 이 아니 라 오류 나 오 류 를 나타 내 는 값 을 되 돌려 더욱 추상 적 인 차원 에서 처리 해 야 한다.
4. 고 효율 과 저 저장량 수요 효율 은 보통 알고리즘 의 집행 시간 을 말한다.저장량 이란 알고리즘 이 실행 과정 에서 필요 한 최대 저장 공간 을 말 하 는데 이들 은 모두 문제 의 규모 와 관계 가 있다.컴퓨터 의 운행 속도 가 매우 빨 라 졌 음 에 도 불구 하고 이런 향상 은 문제 규모 의 증가 로 인 한 속도 요 구 를 만족 시 킬 수 없다.그래서 고속 알고리즘 을 추구 하 는 것 은 여전히 필요 하 다.이에 비해 사람들 은 알고리즘 의 효율 에 더 많은 관심 을 가지 지만 컴퓨터 의 저장 공간 이 대량의 것 이 아니 라 사람들 이 직면 하 는 문제 의 본질 에 의 해 결정 된다.두 사람 은 흔히 한 쌍 의 모순 으로 공간 으로 시간 을 바 꾸 고 시간 으로 공간 을 바 꿀 수 있다.
5. 알고리즘 성능 분석 알고리즘 효율 의 도량 은 알고리즘 의 우열 을 평가 하 는 중요 한 근거 이다.하나의 알고리즘 의 복잡성 높 고 낮 음 은 이 알고리즘 을 실행 하 는 데 필요 한 컴퓨터 자원 의 많 고 적 음 에 나타난다. 필요 한 자원 이 많 을 수록 우 리 는 이 알고리즘 의 복잡성 이 더욱 높다 고 말한다.반대로 필요 한 자원 이 낮 을 수록 이 알고리즘 은 복잡성 이 낮다.가장 중요 한 컴퓨터 자원 은 시간 과 공간 자원 이다.따라서 알고리즘 의 복잡성 은 시간 복잡성 과 공간 복잡성 의 구분 이 있다.
(1) 시간 복잡 도 일반적인 상황 에서 알고리즘 에서 기본 적 인 조작 중복 집행 횟수 는 문제 규모 n 의 특정한 함수 f (n) 이 고 알고리즘 의 시간 도량 은 T (n) = O (f (n) 로 기록 되 며 문제 규모 n 의 증가 에 따라 알고리즘 집행 시간의 성 장 률 은 f (n) 의 성 장 률 과 같 고 알고리즘 의 시간 복잡 도 라 고 부른다.

    ：
                      。

eg: (1) x = x + 1 / / 시간 복잡 도 는 O (1) 로 상수 단계 라 고 합 니 다.(2) for (i = 1; i < = n; i + +) x = x + 1 / / 시간 복잡 도 는 O (n) 로 선형 단계 라 고 부른다.(3)

for(i =1;i<=n;i++) 
         for(j =1;j<=n;j++)
             x=x+1//      O(n ),     。

문제 규모 n 이 계속 커지 면서 상기 시간 복잡 도가 계속 커지 고 알고리즘 의 집행 효율 이 계속 떨어진다.
(2) 공간 복잡 도 는 시간 복잡 도와 비슷 하고 공간 복잡 도 는 알고리즘 이 컴퓨터 에서 실 행 될 때 필요 한 저장 공간의 도량 을 말한다.기록:

S(n)=O(f(n))

알고리즘 이 실행 되 는 동안 필요 한 저장 공간 은 세 부분 을 포함한다. (1) 알고리즘 프로그램 이 차지 하 는 공간
(2) 입력 한 초기 데이터 가 차지 하 는 저장 공간
(3) 알고리즘 실행 과정 에 필요 한 추가 공간
만약 에 입력 데이터 가 차지 하 는 공간 이 문제 자체 에 달 려 있 고 알고리즘 과 무관 하 다 면 입력 과 프로그램 을 제외 한 보조 변수 가 차지 하 는 추가 공간 만 분석 해 야 한다.
필요 한 추가 공간 이 입력 데이터 양 에 비해 상수 라면 이 알고리즘 을 제자리 작업 이 라 고 합 니 다.
필요 한 저장량 이 특정 입력 에 의존 하면 최 악의 경우 에 따라 고려 된다.