Вычислить сложность кода ниже кода

Question

Я чувствую, что и в худшем случае условие выполняется только два раза, когда j = i или j = i ^ 2, тогда l oop выполняется для дополнительно я + я ^ 2 раза. В худшем случае, если мы возьмем сумму внутренних 2 циклов, это будет theta (i ^ 2) + i + i ^ 2, что равно самой theta (i ^ 2); Суммирование тэты (i ^ 2) на внешнем l oop дает тэта (n ^ 3). Итак, является ли ответ тета (n ^ 3)?

Answer 1

Для фиксированных i целых i 1 ≤ j ≤ i<sup>2</sup>, таких что j % i = 0 равны {i,2i,...,i<sup>2</sup>}. Отсюда следует, что внутренний l oop выполняется i раз с аргументами i * m для 1 ≤ m ≤ i, а охранник выполняется i<sup>2</sup> раз. Таким образом, функция сложности T(n) ∈ Θ(n<sup>4</sup>) определяется как:

T(n) = ∑[i=1,n] (∑[j=1,i<sup>2</sup>] 1 + ∑[m=1,i] ∑[k=1,i*m] 1)
     = ∑[i=1,n] ∑[j=1,i<sup>2</sup>] 1 + ∑[i=1,n] ∑[m=1,i] ∑[k=1,i*m] 1
     = n<sup>3</sup>/3 + n<sup>2</sup>/2 + n/6 + ∑[i=1,n] ∑[m=1,i] ∑[k=1,i*m] 1
     = n<sup>3</sup>/3 + n<sup>2</sup>/2 + n/6 + n<sup>4</sup>/8 + 5n<sup>3</sup>/12 + 3n<sup>2</sup>/8 + n/12
     = n<sup>4</sup>/8 + 3n<sup>3</sup>/4 + 7n<sup>2</sup>/8 + n/4

Answer 2

Я бы сказал, что общая производительность составляет theta(n^4). Вот ваш псевдокод, заданный в текстовом формате:

for (i = 1 to n) do
    for (j = 1 to i^2) do
        if (j % i == 0) then
            for (k = 1 to j) do
                sum = sum + 1

Сначала убедитесь, что условие j % i == 0 будет истинным, только если j кратно n. На самом деле это будет происходить только n раз, поэтому окончательный внутренний for l oop будет попадать только n раз, исходя из for l oop в j. Финал для l oop потребует n^2 шагов для случая, когда j находится в конце диапазона. С другой стороны, для начала диапазона потребуется всего примерно n шагов. Таким образом, общая производительность здесь должна быть где-то между O(n^3) и O(n^4), но theta(n^4) должен быть действительным.