자바 균등 하 게 복잡 도와 복잡 도 를 방지 하 는 진동 원리 분석

본 논문 의 사례 는 자바 가 복잡 도 를 균등 하 게 분담 하고 복잡 도의 진동 을 방지 하 는 것 을 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
지난 절패키지 배열 의 간단 하고 복잡 도 분석 방법에서 우 리 는 추가 작업 의 시간 복잡 도 를 O(n)로 요약 하 는 것 은 확장 작업(resize)을 고려 한 것 이다.addLast(e)작업 의 경우 시간 복잡 도 는 O(1)이 고 최 악의 상황 을 고려 할 때 매번 추가 할 때마다 확장 작업 이 발생 하 며 n 개의 요 소 를 이동 해 야 하기 때문에 이때 addLast 작업 의 시간 복잡 도 는 O(n)이다.
(1)addLast(e)평균 분담 시간 복잡 도 분석

resize(n)   O(n)
 현재 capacity=8 을 가정 하고 추가 작업 마다 addLast 방법 을 사용 합 니 다.

17 차 기본 조작 은 9 차 추가 조작,8 차 이전 조작 을 포함한다.평균 할당 매번 addLast 작업 은 약 두 번 기본 작업 을 진행 합 니 다.
평균 값 은 17/9 개 월 2 이다.
  capacity=n,n+1 회 addLast 작업 을 가정 하고 resize 를 촉발 하여 총 2n+1=(n+1)+n 회 기본 작업 을 진행 하 였 습 니 다.
  평균 할당 매번 addLast 작업 은 약 두 번 기본 작업 을 진행 합 니 다.
평균 값: 2n+1 / n+1 ≈ 2
결론:따라서 addLast 평균 분담 시간 복잡 도 는 O(1)이 고 평균 분담 시간 복잡 도 는 최 악의 상황 보다 의미 가 있 습 니 다.일반적인 상황 에서 resize 는 매번 촉발 되 지 않 기 때문에 다른 위 에 분담 할 수 있 습 니 다.
마찬가지 로 removeLast 작업 평균 분담 시간 복잡 도 역시 O(1)
 （1)addLast(e)와 removeLast(e)복잡 도 진동 분석
배열 의 용량 을 n 으로 설정 합 니 다.이때 배열 의 개 수 는 n 개 입 니 다.이때 우 리 는 배열 에 요 소 를 추가 하면 확장 작업 을 촉발 합 니 다.그 다음 에 배열 에서 하나의 요 소 를 삭제 할 때 다시 축소 작업 을 촉발 합 니 다.이렇게 반복 적 으로 실행 하면 O(n)의 복잡 도 를 소모 하여 복잡 도 를 진동 시 킵 니 다.
다음 과 같이 보 여 줍 니 다.
  첫 번 째 addLast(e)시간 복잡 도:O(n)

   두 번 째 실행 removeLast(e)시간 복잡 도:O(n)

  세 번 째 실행 addLast(e)시간 복잡 도:O(n)

   네 번 째 removeLast(e)실행 시간 복잡 도:O(n)

복잡 도 진동 이 발생 하 는 이 유 는 removeLast 시 resize 가 너무 급 하기 때 문 입 니 다(Eager).
해결 방법:Lazy(remove 지연 실행 resize)
  용량 2n,size=n+1 시:
 
 용량 2n,size=n 시 1/2 축소:

 용량 2n,size=1/4*2n,축소 1/2 진행  ：


size==capacity/4 일 때 만 capacity 를 반 으로 줄 입 니 다.
이제 우 리 는 우리 의 프로그램 코드 를 더욱 개선 할 것 이다.

  //      index     ，       
  public E remove(int index) {
    //1.           
    if (index < 0 || index > size)
      throw new IllegalArgumentException("         ");

    //2.              
    E ret = data[index];

    //    index  （index）         
    for (int i = index + 1; i < size; i++) {
      //3.    --      index  （index）         ，     
      data[i - 1] = data[i];
    }
    //4.  size  
    size--;
    // loitering objects != memory leak         
    data[size] = null;

    //    
    if (size == data.length / 4 && data.length != 0) {
      resize(data.length / 2);
    }
    //5.        
    return ret;
  }

 여기까지 우 리 는 비교적 완벽 한 동적 배열 의 패 키 지 를 완성 했다.
자바 관련 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.