#time-complexity #big-o #complexity-theory
#временная сложность #большая ошибка #теория сложности
Вопрос:
int z=1;
for（int i=0;i*i<n;i ）｛
z*=3;
for（int j=0;j<z;j ）{
// Some code
}
}
Ответ — O (3 ^ n).
Это правильно? Как определить временную сложность вложенного цикла?
Ответ №1:
внешний цикл: i переходит от 1 к sqrt (n); внутренний цикл: j, z увеличивается до 3 ^ (sqrt (n));
будет выполняться «некоторый код» 1 3 3^2 … 3^( sqrt(n)) раз
let sum = 1 3 3^2 ... 3^(sqrt(n))
sum - 3*sum = 1 - 3(sqrt(n) 1)
sum = 1 - 3(sqrt(n) 1) / (1-3) = 2( 3^(sqrt(n) 1) - 1 )
2( 3 ^ (sqrt (n) 1) — 1 ) << O ( 3 ^sqrt (n) )
O (3 ^ sqrt (n)) является более точным
Комментарии:
1.
3^sqrt(n)это время выполнения последней итерации внешнего цикла, а не общее выполнение2. пожалуйста, предоставьте более точный ответ для суммирования ряда, который я предоставил. Однако это определенно не O (3 ^ n).
3. нет, ваша сложность правильная, сумма геометрической прогрессии равна
b1*(q^n-1)/(q-1), q=3, которая по-прежнему равна O (3 ^ sqrt (n)), извините за неудобства4. я уточнил разработки, было лениво вводить доказательство
Ответ №2:
Вы могли бы подойти к проблеме, используя сигма-нотацию таким образом:
