평균 복잡성은

Question

선생님은 자신의 평균 복잡성 알아 나에게 아래의 코드를했다 : 나는 코드가 n*(n+1)/2 번 실행하는 발견 루프를 unrowling하여

int function(int a[], int n) 
{ 
    int k=0; 
    for(i=0;i<n;i++) 
     for(j=i+1;j<n;j++) 
      k=k+((a[i]*a[i]+a[j]*a[j])%5==0) 
    return k; 
} 
void main() 
{ 
    int vector={0,1,2,3,4,5,6,7,8,9} 
    int a=function(vector, 10); 
    printf("%d\n", a); 
} 

을 나는 최악의 경우가 결론 O(n^2) 에 대한 n*(n+1)/2 < c*n^2이 존재합니다. 평균 복잡도의 정의가 매우 비슷하지만 계산하기가 어렵다는 것을 알고 있습니다.이 경우 복잡도가 무엇인지, 이러한 유형을 계산하기위한 표준화 된 방법이 있는지 알고 싶습니다. 문제

(예 : 반복자 사이에 종속성이있는 중첩 루프).

Answer 1

평균적인 분석에서 모든 가능한 입력을 가져 와서 모든 입력에 대해 계산 시간을 계산합니다. 계산 된 모든 값을 합계하고 합계를 입력 합계로 나눕니다.

알고리즘에는 단 하나의 가능성 만 있습니다. 모든 입력의 경우 알고리즘은 O (n * (n + 1)/2) 시간으로 실행됩니다.

평균 시간 복잡도는 O (n * (n + 1)/2) = O (n^2)입니다.

Answer 2

계산 복잡도 이론에서 알고리즘의 평균 사례 복잡도는 가능한 모든 입력 see here for definition에 대해 평균화 된 알고리즘에 사용 된 일부 계산 리소스 (일반적으로 시간)의 양입니다.

귀하의 경우, 이미 n * (n + 1)/2 (주어진 n 시간) 동안 귀하의 프로그램이 실행된다는 것을 이미 알고 있습니다. 그렇다면 당신은 생각할 수 있습니다 : 만약 n = 1, 2, 3, ...이라면? 수식을 사용하여 모든 값을 합산하고 평균을 취하면됩니다. O (n^2) 솔루션을 얻는 것은 쉽습니다.