i의 복잡성은 무엇입니까? o = i + 1의 경우

Question

for i = 0 to size(arr) 
    for o = i + 1 to size(arr) 
     do stuff here 

최악의 경우 어떻게됩니까? 두 번째 것은 i 회마다 하나씩 감소하기 때문에 N^2가 아닙니다. 그것은 N이 아니며 더 커야합니다. N-1 + N-2 + N-3 + ... + N-N + 1이다.

Answer 1

은N^2입니다. 두 선형 복잡성의 결과이기 때문에.

는

이 Wikipedia's explanation on the simplifications made을 참조하십시오 (점근 적 복잡성이 점근과 동일하지 을 ...라고하는 이유가있다).

Answer 2

nxn 매트릭스로 작업하는 것처럼 생각하십시오. 대략 행렬 요소의 절반을 다루고 있지만 O (n^2/2)는 O (n^2)와 같습니다.

Answer 3

n*(n-1)/2 이는 O(n^2)과 같습니다.

Answer 4

알고리즘의 복잡도 클래스를 결정하려면 알고리즘의 복잡성 기능에서 가장 빠르게 증가하는 용어를 찾아야합니다. 예를 들어 복잡도 함수가 f(n)=n^2-10000*n+400 인 경우 O(f(n))을 찾으려면 함수에서 "가장 강한"용어를 찾아야합니다. 왜? n은 충분히 커서이 용어 만 전체 함수의 동작을 결정합니다. 그렇다면 f1(n)=n^2-n-4과 f2(n)=n^2이 모두 O(n^2) 인 것을 쉽게 알 수 있습니다. 그러나 동일한 입력 크기 n에 대해 동일한 시간 동안 실행되지 않습니다.

알고리즘에서 n=size(arr) 인 경우 do stuff here 코드는 f(n)=n+(n-1)+(n-2)+...+2+1 번 실행됩니다. f(n)은 산술 시리즈의 합계를 나타내므로 f(n)=n*(n+1)/2 즉 f(n)=0.5*n^2+0.5*n을 쉽게 볼 수 있습니다. do stuff here이 O(1)이라고 가정하면 알고리즘의 복잡도는 O(n^2)입니다.

위한 I = I는 i 같 이하인 size(arr)을되었을 때 루프 종료 것으로 크기 (도착)

에 0. 그러나 후자의 경우는 f(n)=0.5*n^2-0.5*n이며, 여전히 O(n^2)입니다. O(1),O(n),0(n^2), ...은 복잡도 클래스이며 알고리즘의 복잡성 기능은 입력 크기 n에 대해 알고리즘에 몇 단계가 있는지를 설명하는 함수라는 것을 기억하십시오.