배열 이중 루프에서 쌍의 시간 복잡도

Question

나는 다음과 같은 것을 알고 있습니다. 오(n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

하지만 다음과 같아야합니까? count = count + 1; 고려됩니까?복잡한 시간 방정식을 예측 또는 구성하거나 합계 표기법을 사용하려면

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

잘 알려진 태스크 "복제물 확인"이며 예를 들어 Tim RoughGarden - Algorithms illuminated_ Part 1_ 기본 - (2017) 42 페이지에서 찾을 수 있습니다. 마지막 인덱스 "i" $ n= $ "array.length ()"로 마지막으로 인덱스 "i"라고 말합니다. j "는 테두리가 부족합니다. 그러나 이것은 우리의 계산에는 영향을 미치지 않습니다.

항상 주요 주인은 "Count= Count + 1"의 카운트를 선택하는 작업을 선택하는 것입니다. 분명히 가장 좋은 사례, 즉 최소한의 작업은 $ 0 $ 입니다. 그리고 나쁜 경우, 즉 최대 작업량은 합계 (즉, $ n-1 $ )을 $ T (n)= 1 + 2 + \ cdots + (n-1)=frac {n (n-1)} {2} $ (우리는 사례 $ n \ geqslant 2 $ ).

$ \ frac {n (n-1)} {2} \ LeqSlant \ FRAC {n \ cdot 2n} {2}= n ^ 2 $ 은 결론을 내리기 쉽고, 그 악화 $ T (n) \ in o (n ^ 2) $ .

Answer 2

알고리즘의 시간 복잡도는 계산 모델에 따라 다릅니다.알고리즘은 일반적으로 RAM 머신에서 분석되는데, RAM 머신에서는 기계어에 대한 기본 연산(예: 할당, 산술, 비교) 비용이 발생합니다. $O(1)$.기계어에는 길이가 있다 $O(\로그n)$, 어디 $n$ 입력 크기입니다.

귀하의 경우 입력 크기는 최소한 $n$ (의 길이로 정의 array), 그래서 count 단일 기계어에 적합합니다.알고리즘의 각 기본 작업 비용 $O(1)$, 전체 시간 복잡도는 다음과 같습니다. $\세타(n^2)$, 알고리즘이 이렇게 많은 기본 작업을 실행하기 때문입니다.