Frequency Count алгоритмов

Question

мне нужно знать, как определить количество частот суммы: = Sum + 1 заявление в следующей программе:

sum:=0 

for i:=1 to n do 
    for j:=1 to i do 
    for k:=1 to j do 
     sum:= sum+1 
    end<br/> 
    end 
end 

Я также хотел бы знать, как, в общем , чтобы определить частоту всех алгоритмов, а не только одну.

Answer 1

ΣΣΣ 1 = ΣΣ j = Σ (i * (i + 1))/2 = Σ (i^2 + i)/2 = (n (n + 1) (2n + 1)/6 + п (п + 1)/2)/2 = п (п + 1) (п + 2)/6

Ваша формула такова:

F(n) = n(n+1)(n+2)/6 

И в настоящее время не существует общий способ расчета времени работы. Если бы был какой-то способ, теория сложности должна быть удалена из Computer Science.

Answer 2

Для выражения, представляющего точную частоту, вам необходимо обратиться к summation formulas for polynomials.

А именно, внутренние петли зависят от текущей итерации внешних петель. Например:

sum := 0 
for i:=1 to n do 
    for j:=1 to i do 
    sum := sum + 1 

В отношении n, сумма 1 + 2 + 3 + 4 + 5 + ... + п. В обозначениях суммирования это Σ _{i = 1}ⁿ i.

Answer 3

Хорошо, давайте построим это изнутри.

Линия кода выполняется j раз каждый раз, когда выполняется внутренний цикл. Все идет нормально.

Таким образом, каждый раз, когда выполняется средний цикл, мы выполняем оператор 1 + 2 + 3 + ... + i - 1 + i раз. Любой человек должен признать это равным i * (i + 1)/2. Или (i^2 + i)/2

Для каждого запуска внешнего цикла мы выполняем оператор ((1^2+1) + (2^2+2) + ... (n^2+n))/2 раз.

Я оставлю окончательный результат в качестве упражнения для читателя.

Хотя эта проблема неразрешима вообще - если бы вы знали, сколько раз каждая строка кода в программе выполнялась, вы бы решили проблему с остановкой.