algorithm - 算法的平均复杂度

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次，我得出结论，最坏的情况是 O(n^2)因为存在 n*(n+1)/2 < c*n^2对于 n>n0 .我知道平均复杂度的定义很相似，但是我发现很难计算它。我想知道这种情况下的复杂度是多少，是否有计算这类问题的标准化方法

(例如:迭代器之间具有依赖关系的嵌套循环)。

Answer 1

在计算复杂度理论中，算法的平均情况复杂度是算法使用的某些计算资源(通常是时间)的数量，对所有可能的输入进行平均 see here for definition .

在您的情况下，您已经知道您的程序将执行 n*(n+1)/2(对于给定的 n)次。那么你可以想:如果 n = 1, 2, 3, ... 会怎样？您只需要使用您的公式将所有这些值相加并取平均值。很容易得到O(n^2)的解。