У меня есть следующий кодПоказаны порядок роста функции
int sum = 0;
for (int i = 1; i <= n; i = i*2)
{
for (int j = 1; j <=n; ++j)
{
++sum;
}
}
И у меня есть следующий анализ, по мнению некоторых людей, это неправильно, даже если ответ правильный, но я не понимаю, почему ,
Таким образом, я делаю следующее,
n = 1; i = 1; j is being executed 1 time
n = 2; i = 2; j is being executed 2* 1 time
n = 3; i = 4; j = 4 * 3 times
n = 4; i = 8; j = 8 * 4 times
n = 5; i = 16; j = 16 * 5 times
......
n = k; i = 2^k; j = n * 2^k times
И так как 2^к логарифмически (п)
Порядок роста этой функции Nlog (п), который является linearithmic темпы роста ,
Я делаю что-то неправильно в своем анализе? Пожалуйста, дайте мне знать, если у меня есть какие-то ошибки, потому что это меня пугает. Спасибо! Я хочу применить этот анализ к более сложным вложенным циклам, но прежде чем я это сделаю, мне нужно знать, что я делаю неправильно.
Обновление: Я потратил много времени на себя, пытаясь понять, почему мой анализ ошибочен. Благодаря @YvesDaoust, я думаю, что я начинаю понимать это немного больше.
Не оставлять массивную картину код. Отправьте код как текст. – khelwood
Внешний цикл - 'log n', а внутренний цикл равен' n' –
@PeterLawrey Я понимаю, что внешний цикл - это logn, а внутренний цикл - n, но я просто пытаюсь создать анализ, чтобы я мог примените его к более сложным вложенным циклам. – Student