Частота подсчета алгоритмов

Question

Мне нужно знать, как определить счетчик частоты оператора sum: = 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 + n (n + 1) / 2) / 2 = n (n + 1) (n + 2) / 6

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

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

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

Answer 2

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

Строка кода выполняется 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 раз.

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

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

Answer 3

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

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

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

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