Мне нужно рассчитать сложность этого алгоритма:
f=1;
x=2;
for(int i=1;i<=n;i*=2)
for(int j=1;j<=i*i;j++)
if(j%i==0)
for(int k=1;k<=j*i;k++)
f=x*f;
Я понял шаблон и сумму внутреннего цикла, который равен i ^ 2 (i (i + 1)/2), но я не могу получить сумму этого шаблона по ряду (1 2 4 8 16 .. .)
Итак, как я могу найти итог этого ряда?
Я не собираюсь решать это за вас (это похоже на домашнее задание). Но вот подсказка, чтобы упростить задачу.
Этот код:
for(int j=1; j<=i*i; j++)
if(j%i==0)
// ... blah ...
эквивалентен этому коду:
for(int j=i; j<=i*i; j += i)
// ... blah ...
Еще одна подсказка для внешнего for(int i=1;i<=n;i*=2): после каждого выполнения тела цикла for i умножается на 2:
1 · 2 · 2 · … · 2
И так повторяется до тех пор, пока выполняется условие:
1 · 2 · 2 · … · 2 ≤ n
Мы также можем записать повторное умножение двойки следующим образом:
2 · 2 · … · 2 = 2x ≤ n
Сколько раз i умножается на 2, т.е. е. x, можно вычислить с помощью логарифма по основанию 2, i . е. журнал2(n):
2x ≤ n
С x = log2(n) это фактически равно:
2log2(n) = n
Таким образом, условие for является полом (log2(n)) умноженным на истинность, поэтому его сложность равна Ο(log(n)), Ω (log(n)), и, следовательно, θ(log(n)).
