[오늘부터 데이터 구조 수련] 기본 개념.

[오늘부터 데이터 구조 수련] 기본 개념.
[오늘부터 데이터 구조 수련] 선형 표 와 그 실현 및 Itertor 가 있 는 Array List 와 LinkedList 실현
[오늘부터 데이터 구조 수련] 스 택, 피 보 나치 수열, 역 폴란드 사 칙 연산 의 실현
[오늘부터 데이터 구조 수련] 대기 열, 순환 대기 열, Priority Queue 의 원리 및 구현
쌍십 일 저가 로 한 무더기 의 책 을 사 들 였 는데, 오늘까지 미 루 고 아직 보기 시작 하지 않 았 으 니, 정말 해 서 는 안 된다.그래서 오늘부터 데이터 구조 와 알고리즘 을 수련 하고 튼튼한 기 초 를 다 지기 로 했 습 니 다!
학습 노선: 정 걸 과 로 버 트 세 지 윅 두 권 의 책 을 대조 학습 합 니 다.인터넷 에서 수집 한 우수한 박문 참고 까지.코드 는 자바 를 사용 하여 이 박문 을 기록 합 니 다.   —— 2019.11.25  8: 49 B326 실험실 에 있 습 니 다.
그리고 이 두 권 의 책 은 동태 계획 이라는 부분 이 부족 합 니 다. 만약 에 제 수필 을 본 사람 이 있다 면 우수한 동태 계획 강 좌 를 저 에 게 추천 해 주세요 ~
다음은 본 격 적 인 내용 을 시작 하 겠 습 니 다.
데이터 구조
데이터 구 조 를 배 우려 면 먼저 데이터, 데이터 와 관련 된 개념 이 무엇 인지 알 아야 한다.
데 이 터 는 컴퓨터 가 식별 하고 조작 할 수 있 는 기호 집합 이다.　　
데이터 요 소 는 데 이 터 를 구성 하고 일정한 의 미 를 가 진 기본 단위 이다.기록 이 라 고도 불 린 다.
데이터 항목: 하나의 데이터 요 소 는 여러 개의 데이터 항목 으로 구성 할 수 있 습 니 다.  예 를 들 어 사람 이라는 데이터 요 소 는 눈, 귀, 코 등 몇 가지 데이터 항목 이 있 을 수 있다.
데이터 대상 은 성질 이 같은 데이터 요소 의 집합 이다.예 를 들 어 모든 사람 이 눈, 귀, 코 를 가지 고 있 으 면 사람의 집합 은 데이터 대상 이다.
데이터 구조: 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합. 좋 은 프로그램 을 만 들 고 대상 의 특성 과 처리 대상 간 의 관 계 를 분석, 조직, 처리 해 야 합 니 다.
데이터 구 조 는 논리 구조 와 물리 구조 로 나 뉜 다.
논리 구조: 집합 구조  선형 구조  나무 구조  도형 구조
물리 구조: 순차 저장  체인 메모리
고급 언어 에서 데이터 유형 은 원자 유형 (분해 할 수 없 는 기본 유형) 과 구조 유형 (대상, 구조 체 등) 으로 나 눌 수 있다.둘 다 추상 적 인 데이터 형식 에 속한다.추상 적 인 데이터 형식 을 설명 하 는 표준 형식 을 보 여 줍 니 다.
 

ADT        
Data
                 
Operation
      1
            
              
      2
        ……
      n
        ……
endAD

 알고리즘
알고리즘 은 특정 문 제 를 해결 하 는 절차 에 대한 설명 이다.컴퓨터 에서 명령 의 유한 한 서열 로 나타 나 고 모든 명령 은 하나 이상 의 조작 을 나타 낸다.쉽게 말 하면 알고리즘 은 문 제 를 해결 하 는 방법 이다.
좋 은 알고리즘 은 만족 시 켜 야 한다.
1, 정확성
문법 오류 가 없 으 면 합 법 적 인 입력 에 대해 요 구 를 만족 시 키 는 출력 을 할 수 있 습 니 다.불법 입력 에 대해 규격 설명 을 만족 시 키 는 결 과 를 얻 을 수 있다.까다 로 운 테스트 데이터 에 도 만족 하 는 출력 이 있 습 니 다.
2. 가 독성
알고리즘 디자인 의 목적 중 하 나 는 읽 기, 이해 와 교류 에 편리 하 다 는 것 이다.
3, 건장 성 
 좋 은 알고리즘 은 입력 데이터 가 합 법 적 이지 않 은 상황 에 대해 적합 한 처 리 를 할 수 있어 야 지 이상 하거나 이상 한 결과 가 발생 하 는 것 이 아니다.
4. 시간 효율 이 높 고 저장량 이 낮다.
시간 과 공간 복잡 도 분석.사후 통계 방법 은 매우 큰 결함 이 있 고 과학적 이지 않 으 며 정확 하지 않다. 우 리 는 일반적으로 사전 분석 추산 방법 으로 산법 의 효율 을 평가한다.컴퓨터 프로그램 을 작성 하기 전에 통계 방법 에 따라 알고리즘 을 추산 한다.
우리 가 알고리즘 의 운행 시간 을 분석 할 때 중요 한 것 은 기본 작업 의 수량 을 입력 규모 와 연결 시 키 는 것 이다. 즉, 기본 작업 의 수량 은 반드시 입력 규모 의 함수 로 표시 해 야 한다.n 값 이 점점 커지 면서 시간 효율 의 차이 도 점점 커진다.
그렇다면 우 리 는 어떻게 알고리즘 이 시간 적 차 이 를 나타 내 는가?이것 은 알고리즘 시간 복잡 도 를 도입 하 였 다.
 3. 시간 복잡 도
하나의 알고리즘 이 좋 은 지 판단 할 수 있 습 니 다. 우 리 는 소량의 데 이 터 를 통 해 정확 한 판단 을 할 수 없습니다. 우 리 는 알고리즘 의 관건 적 인 집행 횟수 함수 의 점진 적 인 성장 성 을 비교 할 수 있 습 니 다. 특정한 알고리즘 은 n 의 증가 에 따라 다른 알고리즘 보다 점점 우수 해 집 니 다.
하나의 알고리즘 의 효율 을 판단 할 때 함수 중의 상수 와 다른 부차적인 항목 은 항상 무시 할 수 있 으 며, 주 항목 (최고 단계 항목) 의 단계 에 더욱 관심 을 가 져 야 한다.고급 항목 을 분석 하 는 데 관건 은 순환 구조의 운행 상황 을 분석 하 는 것 이다.
알고리즘 의 시간 복잡 도, 즉 알고리즘 의 시간 양 도 는 T (n) = O (f (n) 로 기록 합 니 다.이 는 문제 규모 n 의 증가 에 따라 알고리즘 집행 시간의 성 장 률 과 f (n) 의 성 장 률 이 같 고 알고리즘 의 시간 복잡 도 라 고 부른다.그 중에서 f (n) 는 문제 규모 n 의 특정한 함수 이다.
1. 상수 단계: 단순 한 분기 구조 (순환 구조 에 포함 되 지 않 음) 에 대해 집행 횟수 는 일정 하 며 n 의 변화 에 따라 변화 하지 않 으 며 그 시간 복잡 도 는 O (1) 이다.
2. 선형 단계: 아래 코드 에 대해 순환 체 의 코드 가 n 회 실행 되 어야 하기 때문에 시간 복잡 도 는 O (n) 이다.

int i；
for(i = 0; i < n; i++)

3. 대수 단계: 아래 코드 를 보 세 요.

int count = 1;
while (count < n){
    count  = count * 2;
}

count 는 매번 순환 한 후 2 를 곱 하면 n 에서 배로 가 까 워 집 니 다.2 를 곱 한 후 n 보다 큰 것 이 몇 개 있 으 면 순환 에서 물 러 나 는 것 이다.2x = n 에서 x = log2n.그래서 이 순환 의 시간 복잡 도 는 O (logn) 입 니 다.
4, 제곱 단계: 일반적인 순환 에 끼 워 넣 기

for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
        //  O(1)   
    }
}    

이 코드 의 시간 복잡 도 는 O (n2) 이다.외부 순환 횟수 가 m 로 바 뀌 면시간 복잡 도 O (m)×n).
우 리 는 순환 의 시간 복잡 도 는 순환 체 의 복잡 도 에 이 순환 운행 횟수 를 곱 한 것 과 같다 는 것 을 정리 할 수 있다.
아래 의 이 순환 패 치 를 보 세 요.

for (i = 0; i < n; i++){
    for (j = i; j < n; j++){
　　　　//  O(1)   
     }
}

i = 0 시 내 순환 n 회 실행 하기;i = 1 시, 내부 순환 으로 n - 1 회 실행;...;i = n - 1 시 내 순환 이 한 번 실 행 됩 니 다.그래서 총 집행 횟수 는
　　n + (n - 1 )+ (n - 2) + …… + 1 = n(n + 1)/2 = n2/2 + n/2 .고려 하지 않 는 상 숙, 저급 항 등 을 제거 하고 얻 는 시간의 복잡 도 는 O (n2) 이다.
자주 사용 하 는 시간 복잡 도 에 걸 리 는 시간 은 어 릴 때 부터 크게 다음 과 같다.
　　O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
O (nlogn) 는 뒤에서 토론 하고 보충 을 기다 릴 것 이다.  O (n3) 와 더 높 은 시간 복잡 도가 너무 높 아서 일반적으로 토론 하지 않 는 다.
 실제 상황 에서 만난 문 제 는 모두 좋 고 나 쁨 이 있 을 수 있다.예 를 들 어 배열 에서 순서대로 숫자 를 찾 으 면 가장 좋 은 상황 은 처음에 첫 번 째 위 치 를 찾 는 것 이 목표 이다.최 악의 경우 마지막 위 치 를 찾 아야 목 표를 발견 할 수 있다.그러면 대응 하 는 가장 좋 은 상황 의 시간 복잡 도 는 O (1) 이 고 최 악의 상황 은 O (n) 이다.특별히 지정 되 지 않 는 한 우리 가 언급 한 시간 복잡 도 는 최 악의 상황 에 따라 고려 되 는 운행 시간 이다.그러면 저희 가 알고리즘 을 디자인 할 때 원 하 는 시간 은 어떤 운행 시간 입 니까?우리 가 원 하 는 것 은 평균 운행 시간 이다. 위의 예 는 n/2 이다. 평균 운행 시간 은 모든 상황 에서 가장 의미 가 있다. 왜냐하면 그것 은 기대 하 는 운행 시간 이기 때문이다.
 4. 공간 복잡 도
우 리 는 코드 를 쓸 때 공간 으로 시간 을 바 꿀 수 있다.예 를 들 어 어느 해 가 윤년 인지 아 닌 지 를 판단 해 야 한다. 일반적인 방법 일 때 알고리즘 을 쓰 고 판단 조건 을 설정 하여 윤년 인지 아 닌 지 를 계산 해 야 한다.또 다른 방법 은 2050 개 원소 의 수 조 를 설정 하여 모든 연 도 를 아래 표 에 따라 대응 하 는 것 이다. 윤년 이 라면 수조 값 을 1 로 설정 하고 값 을 0 으로 설정 하지 않 으 면 윤년 인지 아 닌 지 를 수조 에 직접 가서 아래 표 에 따라 값 을 추출 할 수 있다.이렇게 하면 우리 의 운행 시간 은 O (1) 이지 만 하드디스크 나 메모 리 는 이러한 긴 그룹 을 저장 해 야 한다.이것 이 바로 공간 을 시간 으로 바 꾸 는 방법 이다.
도대체 뭐 가 좋아요?어디 에 쓸 지.
알고리즘 의 공간 복잡 도 는 계산 알고리즘 에 필요 한 저장 공간 을 통 해 이 루어 집 니 다. 알고리즘 화살 복잡 도의 계산 공식 은 S (n) = O (f (n) 로 기 록 됩 니 다.n 은 문제 규모 이 고 f (n) 는 n 이 차지 하 는 저장 공간 에 대한 함수 입 니 다.