자바 패키지 배열 에 대한 간단 한 복잡 도 분석 방법

본 논문 의 사례 는 자바 가 패 키 징 배열 에 대한 간단 하고 복잡 도 분석 방법 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
배열 의 포장 을 완성 한 후에 우 리 는 그것 에 대해 복잡 도 분석 을 해 야 한다.
이곳 의 복잡 도 분석 은 주로 시간 복잡 도 분석 을 말한다.알고리즘 의 시간 복잡 도 는 프로그램 집행 시간 이 입력 규모 의 증가 에 따라 증가 하 는 양 급 을 반영 하고 어느 정도 에 알고리즘 의 우열 여 부 를 잘 나 타 낼 수 있다.
1.단순 개념
여러 가지 서로 다른 알고리즘 에서 만약 에 알고리즘 에서 문장의 집행 횟수 가 상수 라면 시간 복잡 도 는 O(1)이다.또한 시간 빈도 가 다 르 면 시간 복잡 도 는 같 을 수 있다.예 를 들 어 T(n)=n2+3n+4 는 T(n)=4n2+2n+1 과 그들의 빈도 가 다 르 지만 시간 복잡 도 는 같 고 모두 O(n2)이다.수량 급 에 따라 점차적으로 배열 하면 흔히 볼 수 있 는 시간 복잡 도 는 상수 단계 O(1),대수 단계 O(log2n),선형 단계 O(n)가 있다. 선형 대수 단계 O(nlog2n),제곱 단계 O(n2),입방 단계 O(n3),...,k 차방 단계 O(nk),지수 단계 O(2n).문제 규모 n 이 계속 커지 면서 상기 시간 복잡 도가 계속 커지 고 알고리즘 의 집행 효율 이 낮다.관련 그림 은 다음 과 같다.

   그림 에서 볼 수 있 듯 이 우 리 는 가능 한 한 여러 단계 의 O(nk)알고리즘 을 사용 해 야 하 며 지수 단계 의 알고리즘 을 사용 하 는 것 을 원 하지 않 는 다.
보 이 는 알고리즘 시간 복잡 도 는 작은 것 에서 큰 것 으로 다음 과 같다.Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)
 2.대 O 단순 정의(비 수학 영역)
 큰 O 는 알고리즘 운행 시간 과 입력 데이터 간 의 관 계 를 묘사 합 니 다.
3.단순 프로그램 시간 복잡 도 분석

상기 에서 알고리즘 과 n 은 선형 관 계 를 나타 내 는데 왜 큰 O 를 사용 합 니까?O(n)라 고 하나 요?
사실 상기 프로그램 에서 실제 시간 복잡 도:T=c1*n+c2 는 상수 c1 과 c2 를 무시 합 니 다.
따라서 알고리즘 은 N 과 선형 관 계 를 가지 고 n 의 고급 항목 을 취한 다.n 이 무한대 로 변 할 때 낮은 단계 의 역할 이 매우 작 기 때문이다.
4.동적 배열 의 시간 복잡 도 를 분석한다.
(1)동적 배열 추가 작업 시간 복잡 도 분석
(1)addLast(e)방법:마지막 위치 에 만 추가   시간 복잡 도 O(1)
(2)addFirst(e)방법,배열 에서 한 자 리 를 뒤로 이동 해 야 합 니 다.   시간 복잡 도 O(n)
(3)add(index,e)방법 은 index 위치 에 e 를 삽입 하고 시간 복잡 도 는 선택 한 위치 와 관련 이 있 으 며 마지막 시간 복잡 도 를 O(1)로 선택한다.첫 번 째 위 치 를 선택 하 십시오.시간 복잡 도 는 O(n)입 니 다.기타 상황 은 확률 과 관련 이 있 으 며,평균 상황 에서 n/2 개 위치 만 이동 하면 된다.   시간 복잡 도 는 O(n/2)=O(n)
전체적으로 말 하면 배열 이 추 가 된 시간 복잡 도 는 O(n)(최 악의 경우 고려)이다.
추가 할 때 resize 방법 이 실 행 될 수 있 습 니 다.n 개의 요 소 를 새 배열 로 이동 해 야 합 니 다.   시간 복잡 도 O(n)

 （2)동적 배열 삭제 작업 시간 복잡 도 분석
 같은 분석 방법 으로 삭제 작업 의 시간 복잡 도 를 얻 을 수 있다.

(3)동적 배열 수정 작업 시간 복잡 도 분석
 수정 에 대해 서 는 색인 을 통 해 찾 으 면 수정 할 수 있 으 며 시간 복잡 도 는 O(1)이다.

(4)동적 배열 찾기 작업 시간 복잡 도 분석

동적 배열 시간 복잡 도 분석 총화:

resize 방법 에 대해 우 리 는 최 악의 상황 분석 을 완전히 사용 하 는 것 은 불합리 합 니 다.그 분석 상황 은 다음 절 에 학습 할 것 입 니 다~
자바 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.