Анализ сложности времени - PullRequest
0 голосов
/ 10 ноября 2019

Я пытаюсь проанализировать некоторые алгоритмы, используя методы констант, и я не уверен, правильно ли я это делаю, поэтому я публикую здесь алгоритм и мою попытку:

Sum(A[0..n], n)                       | Cost           Freq
s = 0                                 | c1             1
for i = 1..n                          | c2             n
    if A[i] > 0                       | c3             n - 1
        for j = 1..i                  | c4             sum_{i = 1}^n t_i*i
            if A[j] mod 2 == 0        | c5              x
                for k = 1..j          | c6              y
                    s = s + i + j + k | c7              z
        }
return s

x

y

z

С t_i логическим значениемсостояние A[i] > 0, t_i ∈ {0, 1}. С p_j логическим значением условия A[i] mod 2 == 0, p_j ∈ {0, 1}

...