자바 데이터 구조 기초:알고리즘

데이터 구조 와 알고리즘 관계
이 제목 을 데이터 구조 라 고 부 르 지만 저 는 알고리즘 을 정리 합 니 다.나 는 뽑 을 일이 없 는 것 이 아니 라,단지 데이터 구 조 를 배 울 때,알고리즘 은 네가 틀림없이 떠 날 수 없 는 것 이다.
당신 이 평소에 인터넷 에서 본 글 들 은 당신 이 무심코 검색 할 때 모두 검색 한 데이터 구조 와 알고리즘 이라는 일곱 글자 가 아 닙 니까?이것 이 무엇 을 설명 하 는 지,이것 은 그들 둘 이 떠 날 수 없다 는 것 을 설명 한다.
예 를 들 어 덕 운사 만담 을 보고 싶 습 니 다.그런데 정원 에 들 어가 보 니 그들 이 오늘 병 이 났 어 요.다른 사람들 로 바 뀌 었 어 요.즐 거 우 셨 어 요?즐 겁 지 않 았 어 요?
그래서 데이터 구조 와 알고리즘 도 마찬가지다.그 중 어느 것 도 없 으 면 안 된다.
그러나 대학 안의 개념 적 인 것 에 따 르 면 우리 학교 와 비슷 하고 알고리즘 은 단독으로 과정 을 개설 하 는 것 이지 데이터 구조 와 함께 하 는 것 이 아니다.그래서 이 장 은 이론 이다.
가우스
틀림없이 이곳 을 본 사람 은 틀림없이 이 사람 에 대해 일찍이 들 은 적 이 있 을 것 이다.
만약 당신 에 게 누차 화 해 를 구하 라 고 한다 면,당신 은 반드시 이런 코드 를 쓸 것 입 니 다.

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

이렇게 하 는 것 은 확실히 맞 지만 문제 가 생 겼 다.너 는 이것 과 몇 번 이나 순환 하 였 니?틀 리 지 않 았 다 면 101 번 이 었 겠 죠.왜 냐 면,당신 은 매번 누적 할 때마다 for 순환 을 한 번 씩 걷 기 때 문 입 니 다.그러면 불필요 한 시간 을 평온하게 늘 려 연산 할 수 있 습 니 다.당신 은 이 시간 이 있 으 면 아 소 를 빼 앗 을 수 없습니다.
우 리 는 이 천재 가 당시 에 어떻게 했 는 지 직접 보 았 다.
sum=1+2+3+...+100 이 니까 요.
그런데 sum=100+99+98+...+1
둘 을 합치 면 2sum=101+101+101+...+101
101,100 개가 몇 개 죠?그럼 2 를 빼 면 5050 이 잖 아 요.코드 로 어떻게 써 요?

int i=0;
int sum=0
int n=100;
sum=(1+n)*n/2

이것 이 바로 신동 입 니 다.이것 이 바로 큰 사람 입 니 다.문 제 를 생각 하 는 부분 은 모두 우리 와 다 릅 니 다.
즉,이런 방식 으로 우 리 는 그 100 번 의 불필요 한 연산 을 생략 하고 한 번 의 연산 만으로 도 답 을 얻 을 수 있다 는 것 이다.
1 억 원 넣 으 라 고 하면?어떤 효율 이 더 높 을 지 생각해 봐.
알고리즘 정의
알고리즘 이라는 단 어 는 서기 825 년 에 아 레 화 라 라 라 는 페르시아 수학자 가 쓴 에서 최초 로 제기 되 었 다.
현재 로 서 는 보편적 인 정 의 는:
알고리즘 은 특정한 문 제 를 해결 하 는 절차 에 대한 설명 으로 컴퓨터 에서 명령 의 유한 한 서열 로 나타 나 고 모든 명령 은 하나 또는 여러 개의 조작 을 나타 낸다.
방금 전의 문 제 를 우리 도 보 았 는데,한 문제 에 대해 여러 가지 방법 으로 답 을 풀 수 있다.그럼 문제 가 생 겼 습 니 다.통용 되 는 알고리즘 이 있 습 니까?
이 답 은 사실 당신 이 병원 에 가서 약 을 사 는 것 과 같 습 니 다.모든 병 을 치료 할 수 있 는 약 답 이 있 습 니까?
알고리즘 특성
알고리즘 은 다섯 가지 특성 을 가지 고 있 습 니 다.입력,출력,유한,확정,실행 가능 합 니 다.
입 출력
이 건 이해 하기 쉬 워.알고리즘 은 0 개 또는 여러 개의 입력 을 가지 고 있다.
궁성 이 있다
알고리즘 이 제 한 된 절 차 를 실행 한 후에 무한 순환 이 나타 나 지 않 고 모든 절 차 를 받 아들 일 수 있 는 시간 안에 완성 하 는 것 을 말한다.
물론 이곳 의 가난 은 실제 적 인 의미 에서 합 리 적 이라는 것 을 말한다.
타당 성
알고리즘 의 모든 단 계 는 반드시 실행 할 수 있어 야 한다.즉,모든 단 계 는 제 한 된 횟수 를 통 해 완성 할 수 있다.
알고리즘 설계 의 요구
방금 우리 가 말 했 듯 이 알고리즘 은 결코 유일한 것 이 아니다.그러면 우 리 는 한 문 제 를 처리 할 때 반드시 사전에 알고리즘 을 잘 설계 해야만 문 제 를 해결 할 수 있다.
정확성
알고리즘 의 정확성 이란 알고리즘 이 적어도 입 출력 과 가공 공장 에서 처리 해 야 하 는 잘못된 의미 가 없고 문제 의 수 요 를 정확하게 반영 할 수 있 으 며 개가 문 제 를 얻 을 수 있 는 정확 한 답 을 가 져 야 한 다 는 것 을 말한다.
가 독성
알고리즘 디자인 의 또 다른 목적 은 읽 기,이해 와 교 류 를 편리 하 게 하기 위 한 것 이다.
너 는 네가 매우 강 한 코드 를 썼 다 고 말 했 는데,다른 사람 이 알 아 볼 수 없 는데,어떻게 네가 강 한 것 을 인정 하 겠 니?그렇지?
건장 성
입력 데이터 가 합 법 적 이지 않 을 때 알고리즘 도 이상 하거나 이상 한 결과 가 발생 하 는 것 이 아니 라 해당 하 는 처 리 를 할 수 있다.
시간 효율 이 높 고 저장량 이 낮다.
알고리즘 디자인 은 시간 효율 이 높 고 저장량 이 낮은 특징 을 최대한 만족 시 켜 야 한다.
이 점 에 나 는 좀 처럼 도달 하지 못 했다.
알고리즘 효율 의 도량형 방법
알고리즘 의 효율 은 알고리즘 의 집행 시간 을 가리킨다.그럼 우 리 는 어떻게 그의 집행 시간 을 계산 합 니까?
가장 간단 한 방법 은 컴퓨터 의 시간 측정 기능 으로 서로 다른 알고리즘 을 계산 하 는 효율 이 높 은 지 낮은 지 하 는 것 이다.
사후 통계 법
설 계 된 테스트 프로그램 과 데 이 터 를 통 해 컴퓨터 타 이 머 를 이용 하여 서로 다른 알고리즘 으로 제 작 된 프로그램의 운행 시간 을 비교 하여 알고리즘 효율 의 높 고 낮 음 을 확인한다.
그러나 이런 방법 은 매우 큰 결함 이 있다.
사전 분석 추산 방법
컴퓨터 프로그램 을 작성 하기 전에 통계 방법 에 따라 알고리즘 을 추산 한다.
분석 을 통 해 고급 프로그램 언어 로 작 성 된 프로그램 이 컴퓨터 에서 실 행 될 때 소모 되 는 시간 은 다음 과 같 습 니 다.
알고리즘 이 사용 하 는 전략,방법컴 파일 된 코드 품질
문제 의 입력 규모
기계 가 명령 을 집행 하 는 속도사실 너 는 이 위의 네 가지 중 어느 것 이 가장 중요 한 지 생각해 봐 라.문제 의 입력 규모 일 뿐이다.
입력 규모 란 입력 량 의 크기 이다.
우 리 는 방금 전의 고 스 구 화 를 다시 분석 해 보 자.
첫 번 째 종류:

int sum=0; //    1 
int n=100; //      
for(int i=0;i<=n;i++){ //    n+1 
sum+=i; //    n 
}

두 번 째:

int sum=0; //      
int n=100; //    1 
sum=(1+n)*n/2; //    1 

어느 것 이 좋 고 어느 것 이 나 쁜 지 이제 알 수 있 겠 지?
우 리 는 파생 알고리즘 을 하나 더 보 자.

int i;
int j;
int x=0;
int sum=0;
int n=100;
for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
		x++;
		sum+=x;
	}
}

이 예 는 이해 하기 쉽 습 니 다.사실은 백 번 더 순환 한 것 일 뿐 입 니 다.그러면 마지막 으로 계산 한 횟수 는 얼마 입 니까?n²，맞 죠?
우 리 는 프로그램 이 사용 하 는 어떤 언어,어떤 기계 에서 실행 하 는 지 에 관심 이 없고 알고리즘 에 만 관심 이 있다.최종 적 으로 프로그램의 운행 시간 을 분석 할 때 가장 중요 한 것 은 프로그램 을 프로그램 설계 에 독립 된 알고리즘 이나 일련의 절차 라 고 할 수 있다.
문제 에서 시사 점 을 얻 을 수 있다.같은 규 모 는 모두 n 을 입력 하고 알고리즘 과 다 르 기 때문에 이 운행 효율 도 다르다.
첫 번 째 총 결 은 f(n)=n 이다.
두 번 째 는 간단 하 다.바로 f(n)=1 이다.세 번 째 는 요?f(n)=n²
한 장의 그림 으로 보 여 드릴 까요?(네트 웍

함수 의 점진 적 증가
우 리 는 지금 예 를 들 어 두 개의 알고리즘 a 와 b 중 어느 것 이 더 좋 습 니까?두 알고리즘 의 입력 규모 가 모두 n 이 라 고 가정 하면 알고리즘 a 는 2n+3 번 조작(두 번 n 순환,3 번 연산)을 하고 알고리즘 b 는 3n+1 번 조작 을 해 야 한다.
시계 한 장 으로 시범 을 보이다.
횟수
알고리즘 a(2n+3)
알고리즘 a'(2n)
알고리즘 b(3n+1)
알고리즘 b'(3n)
n=1
5
2
4
3
n=2
7
4
7
6
n=3
9
6
10
9
n=10
23
20
31
30
n=100
203
200
301
300
이 표를 보면 마지막 으로 우 리 는 알고리즘 a 가 전체적으로 알고리즘 b 보다 우수 하 다 는 것 을 정리 해 냈 다.
입력 규모 n 은 제한 이 없 는 상황 에서 하나의 수 n 을 초과 하면 이 함 수 는 항상 다른 함수 보다 크다.우 리 는 점진 적 인 성장 이 라 고 부른다.
함수 의 점진 적 인 증가:두 함수 f(n)와 g(n)을 지정 합 니 다.하나의 정수 N 이 존재 하면 팀 닥 터 의 모든 n>N,f(n)가 항상 g(n)보다 크 면 f(n)의 점진 적 인 성장 이 g(n)보다 빠르다 고 합 니 다.
그 중에서 우 리 는 n 이 커지 면서 뒤의+3 또는+1 은 최종 결과 에 영향 을 주지 않 기 때문에 우 리 는 이런 상수 들 을 무시 할 수 있다.우 리 는 두 번 째 예 를 다시 보 자.
횟수
알고리즘 c(4n+8)
알고리즘 c'(n)
알고리즘 d(2n²+1)
알고리즘 d'(n)²)
n=1
12
1
3
1
n=2
16
2
9
4
n=3
20
3
19
9
n=10
48
10
201
100
n=100
408
100
20 001
10 000
n<=3 일 때 알고리즘 c 는 알고리즘 d 보다 못 하지만 n>3 이후 에 우세 가 나타 나 기 시작한다.
그래서 마지막 으로 최고 차 항의 상수 와 는 중요 하지 않다.
사실은 이 두 표 에 따라 대체적으로 분석 할 수 있다.특정한 알고리즘 은 n 이 커지 면서 그 는 다른 알고리즘 보다 우수 하거나 다른 알고리즘 보다 점점 떨어진다.
이것 은 바로 사전 추산 방법의 이론 적 근거 로 알고리즘 시간 복잡 도 를 통 해 시간 효율 을 추산 하 는 것 이다.
알고리즘 시간 복잡 도
정의:알고리즘 분석 을 할 때 문장의 실행 횟수 T(n)는 문제 규모 n 에 관 한 함수 로 T(n)가 n 의 변화 상황 에 따라 T(n)의 수량 급 을 확인한다.알고리즘 의 시간 복잡 도,즉 알고리즘 의 시간 양 도 는 T(n)=O(f(n)로 기록 합 니 다.그 는 문제 규모 n 이 커지 면서 알고리즘 집행 시간의 성 장 률 은 f(n)의 성 장 률 과 같 고 알고리즘 의 점진 적 시간 복잡 도 라 고 부 르 며 시간 복잡 도 라 고 부른다.그 중에서 f(n)는 문제 규모 n 의 특정한 함수 이다.

총결산
이 글 은 여기까지 입 니 다.당신 에 게 도움 을 줄 수 있 기 를 바 랍 니 다.또한 당신 이 우리 의 더 많은 내용 에 관심 을 가 져 주 실 수 있 기 를 바 랍 니 다!