平均複雑さは

Question

先生は私に彼の平均複雑さを見つけるために以下のコードを与えた：

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); 
} 

私はコードがn*(n+1)/2回を実行し、私は最悪のケースであると結論づけることが判明ループをunrowlingすることによりO(n^2) .I n>n0ためn*(n+1)/2 < c*n^2は平均複雑さの定義は非常に似ていることを知っているが、私はit.Iが、この場合のこれらのタイプを計算するための標準化された方法がある場合は複雑であるかを知りたい計算するのは非常に困難見つけ存在するため、問題

（例：イテレータ間の依存関係を持つネストされたループ）。

Answer 1

平均的な分析では、可能なすべての入力を取り、すべての入力の計算時間を計算します。すべての計算値を合計し、合計を入力数で除算します。

アルゴリズムには1つの可能性しかありません。 すべての入力の場合、アルゴリズムはO（n *（n + 1）/ 2）時間で実行されます。

平均時間計算量はO（N *（N + 1）/ 2）= O（N^2）です。

Answer 2

計算複雑性理論では、アルゴリズムの平均ケース複雑度は、アルゴリズムによって使用されるいくつかの計算リソース（通常は時間）の量であり、可能なすべての入力に対して平均化されています。see here for definition。あなたのケースでは

は、あなたはすでにあなたのプログラムは、（与えられたn個の場合）のn *（n + 1）/ 2個の回実行されることを考え出しました。次に、あなたは考えることができます：もしn = 1,2,3、...なら？数式を使用してこれらの値をすべて加算し、平均します。 O（n^2）の解を得るのは簡単です。