Средняя сложность алгоритма

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

По unrowling петли я обнаружил, что код выполняется n*(n+1)/2 раз, и я делаю вывод, что худший случай O(n^2) потому что существует n*(n+1)/2 < c*n^2 для n>n0. Я знаю, что определение средней сложности довольно похоже, но мне было довольно сложно вычислить его. Я хочу знать, в чем сложность в этом случае, и если существуют стандартизированные методы для вычисления этих типов проблемы

(например: вложенные петли с зависимостями между итераторами).

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).