데이터 구조 와 알고리즘 - 기본 지식

데이터 구 조 는 모든 프로그래머 에 게 필수 적 인 기초 이자 각 회사 의 면접 에서 중요 하 다.그리고 저 는 초보 자로 서 자바 버 전의 데이터 구 조 를 배 우려 고 합 니 다. 그래서 저 는 깊이 공부 하고 코드 로 각종 데이터 구 조 를 실현 하려 고 합 니 다. 제 가 작성 한 이 일련의 블 로 그 는 저 처럼 데이터 구 조 를 잘 모 르 는 초보 자 에 게 도움 을 줄 수 있 기 를 바 랍 니 다. 만약 에 오류 가 있 으 면 여러분 께 서 말씀 해 주 십시오. 저 는 감사 하 겠 습 니 다.
1. 데이터 구조 와 알고리즘 의 개념
데이터 구 조 는 현실 의 데 이 터 를 컴퓨터 에 어떻게 저장 하 는 지 연구 하 는 것 으로 데이터 간 에 특정한 논리 적 관 계 를 가지 게 하여 사람들 이 이 데 이 터 를 효과적으로 방문 하고 처리 할 수 있다.데이터 구조 에서 주로 이 네 가지 저장 구조 가 존재 하 는데 그것 이 바로 순서 구조, 체인 구조, 산열 구조 와 색인 구조 이다.알고리즘 은 데 이 터 를 처리 하 는 방법 이자 프로그래머 가 문 제 를 해결 하 는 방법 과 사고 이다. 알고리즘 의 효율 은 데이터 의 처리 속 도 를 결정 하 는 동시에 프로그래머 의 능력 도 나타 내 므 로 알고리즘 은 모든 프로그래머 에 게 매우 중요 하 다.저 는 프로 그래 밍 의 가장 중요 한 것 은 문 제 를 해결 하 는 능력, 즉 사고 와 방법 이 라 고 생각 합 니 다. 그 다음 에 coding 의 과정 이 라 고 생각 합 니 다. coding 은 현실 의 사물 을 코드 의 형식 으로 바 꾸 고 단련 할 수 있 기 때문에 우 리 는 자신의 논리 적 사고력 을 키 우 는 것 을 중시 해 야 합 니 다. 개인 적 인 견 해 를 가지 고 뿌 려 서 는 안 됩 니 다.알고리즘 이 가 져 야 할 5 가지 특성 은 모두 가 알 고 있 을 것 이다. (1) 가난 성 이 있다. 하나의 알고리즘 은 반드시 일정한 절 차 를 실행 한 후에 끝내 야 한다. 그렇지 않 으 면 프로그램 이 순환 하지 않 는 다.(2) 확정 성: 알고리즘 중의 모든 단 계 는 정확 한 의 미 를 가 져 야 한다.컴퓨터 는 기계 이 고 프로그램 은 어떻게 가 는 지 알려 주 는 것 이다. 그렇지 않 으 면 방향 을 잃 을 것 이다. 인간 처럼 똑똑 하지 않다. 하하.(3) 타당 성: 알고리즘 중의 모든 단 계 는 반드시 실행 가능 해 야 한다. 즉, 모든 단 계 는 제 한 된 시간 안에 완성 할 수 있 고 무한 한 집행 이 아니 라 의미 가 없다.(4) 입력: 하나의 알고리즘 은 0 개 이상 의 입력 이 가능 합 니 다.(5) 출력: 하나의 알고리즘 은 적어도 하나의 출력 이 있다.출력 이 없 으 면 이 알고리즘 은 모 용이 있 습 니 다!
2. 알고리즘 평가
알고리즘 평 가 는 알고리즘 의 좋 고 나 쁨 을 평가 하 는 것 이다.보통 한 가지 일 에 대해 다양한 처리 방법 이 있 기 때문에 우 리 는 가장 좋 은 해결 방안 을 선택 할 것 이다.예 를 들 어 베 이 징 에 가면 서로 다른 지역 의 사람들 이 서로 다른 이동 방식 을 가 질 수 있다. 천진 에 대해 자가 운전 은 베 이 징 에 도착 하 는 가장 빠 른 방식 일 수 있 고 고속 철 도 를 타면 많은 대기 시간 을 들 일 수 있다.산동 에 서 는 고속 철도 가 가장 빠 를 수 있 고 하 이 난 에 서 는 비행기 가 가장 빠 를 수 있다.따라서 코드 를 작성 할 때 알고리즘 의 우열 을 고려 해 야 합 니 다.일반적으로 우 리 는 5 가지 기준 으로 알고리즘 을 평가 하 는데 그것 이 바로 정확성, 건장 성, 가 독성, 시간 복잡 도와 공간 복잡 도 이다.앞의 세 가지 지 표 는 모두 가 이해 할 수 있어 야 한다. 다음은 시간 복잡 도와 공간 복잡 도 에 대해 설명 하 는 데 중심 을 두 어야 한다.　　
1. 시간 복잡 도:
시간 복잡 도 는 알고리즘 이 처음부터 끝까지 실 행 된 시간 을 나타 낸다. 일반적으로 프로그램 이 간단 한 조작 을 한 번 수행 하 는 데 걸 리 는 시간 은 같다. 예 를 들 어 가감 승제, 할당 조작 등 이다. 따라서 알고리즘 의 시간 복잡 도 는 코드 에서 간단 한 조작 연산 횟수 를 합 친 것 을 말 하 는데 보통 O (Order: 수량 급) 로 표시 한다.시간 복잡 도 는 보통 O (1), O (n), O (log2n), O (nlog2n), O (n2), O (n3), O (2n), O (n!) 등 형식 으로 최고 차 멱 으로 표시 한다. 다음은 몇 가지 흔히 볼 수 있 는 예 를 들 어 알고리즘 의 시간 복잡 도 를 살 펴 보 자.

그 중에서 O (1) 는 시간 운행 이 고정 적 이라는 것 을 나타 내 고 보통 간단 한 할당 문 과 출력 문, 즉 운행 시간 은 상수 이다.

순환 문장의 시간 복잡 도 는 보통 O (n), O (n2), O (n3) 이다. 예 는 다음 과 같다.

int n = 100;
int count = 0;
for (int i = 0; i < n; i++) {
    count++;
}

이 알고리즘 의 연산 횟수 는 n + 2 이 며, 최고 차 멱 을 취하 고, 복잡 도 는 O (n) 이다.

int n = 100;
int count = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        count++;
    }
}

이 알고리즘 은 2 중 for 순환 이 고 연산 횟수 는 n2 + 2 이 며 시간 복잡 도 는 O (n2) 이다.

복잡 도가 O (log2n) 인 고전 알고리즘 은 2 점 검색 입 니 다.

int[] array = {1,2,3,4,5,6,7,8};    //          ,      
int k = array.length/2; //            
int dest = 5;   //        ,            ， dest      
while(true){    //   
    if(array[k]==dest){
        System.out.println(dest);
        break;  //    
    }
    if(array[k]>dest){  //  dest  array[k],
        k = k/2;
    }
    if(array[k]array.length)/2;
    }
}

2. 공간 복잡 도
공간 복잡 도 는 일반적으로 하나의 알고리즘 이 실행 과정 에서 저장 공간 크기 를 임시로 차지 하 는 양 을 말한다. 하나의 알고리즘 이 컴퓨터 메모리 에서 차지 하 는 저장 공간 은 저장 알고리즘 자체 가 차지 하 는 저장 공간, 알고리즘 의 입 출력 데이터 가 차지 하 는 저장 공간 과 알고리즘 이 실행 과정 에서 임시로 사용 하 는 저장 공간 등 세 가지 측면 을 포함한다.일부 상황 에서 알고리즘 의 공간 복잡 도 는 임시 점용 저장 공간 을 나타 내 고 복잡 도 는 보통 O (1) 이다.

int a = 10;
int b = 20;
int temp = a;   
a = b;
b = temp;

상기 알고리즘 은 두 변수 내용 의 교환 을 실현 하기 위해 temp 를 임시 저장 공간 으로 정의 하기 때문에 이 알고리즘 의 공간 복잡 도 는 O (1) 이다.
3. 총화
기본 개념 을 이해 하 는 것 은 데이터 구 조 를 깊이 공부 하 는 것 이 필수 조건 입 니 다. 또한 알고리즘 을 만 드 는 데 있어 서 우 리 는 시간 복잡 도와 공간 복잡 도 를 결합 시 켜 효율 을 극 대화 해 야 합 니 다. 이 블 로 그 를 만 드 는 것 도 시간 복잡 도 를 깊이 이해 하고 데이터 구 조 를 실현 하 는 구체 적 인 조작 방법 입 니 다. 주목 하 세 요!