Определение асимптотической сложности в наихудшем случае (O (N)) конкретной функции
Я хотел бы определить асимптотическую сложность в худшем случае следующую функцию:
int j;
float r = 1.0;
for (int i=1; i<(log n); i++){
j = 1;
while (j <= i^2){
r*=2;
j++;
}
print(r);
Решение
Во-первых, я предполагаю, что i^2 в твоем коде значит «i возведен в степень 2 «, а не»i bitwise-XOR 2 «, так как последний соответствует синтаксису C ++, но дает непредсказуемые результаты.
Временная сложность определяется суммой
Нам нужно оценить суммы натуральных чисел до степени 2, используя информацию с этой веб-страницы: http://www.trans4mind.com/personal_development/mathematics/series/sumGeneralPowersNaturalNumbers.htm.
Таким образом, сложность времени
Другие решения
Других решений пока нет …