Сколько раз функция будет вызываться?

Вот у меня есть цикл:Сколько раз функция будет вызываться?

for (i = n; i < 2*n; i += 4) { 
    for (j = 0; j < 3*i; j += 2) { 
     function(); 
    } 
}

Как я могу подсчитать количество вызовов (в перспективе п) функции() без выполнения этого кода?

Как я думаю, я могу использовать арифметическую прогрессию, которая имеет сумму S = (a1 + ak) * k/2, где a1 - количество итераций внутреннего цикла, когда i имеет начальное значение, ak - это количество итераций внутреннего цикла, в то время как у меня есть конечное значение.

Но я не могу выразить его как одну формулу с n как переменной.

У вас есть идеи по этому поводу?

источник

2014-01-15 Felix Vein

если я использую O (n) обозначение - это будет O (n^2). но мне нужно выразить точную формулу, которая будет подсчитывать, сколько раз функция() подсчитывается –

. Ваше название не имеет особого значения, но я не могу сказать, что я могу думать о лучшем. – Dukeling

@FelixVein Вы уже некоторое время отправляете эту домашнюю работу, и более того, я думаю, что это математическая проблема, а затем алгоритмическая. –

Ну, у вас есть формула для арифметической прогрессии. Когда i = n, внутренний цикл равен 3n/2 раза (более или менее - вам может потребоваться преобразовать в целое число). Возможно, вам придется немного настроить верхний бит, потому что нет гарантии, что n делится на 4, но вы можете сделать то же самое для заключительного цикла. И он будет работать n/4 раза (снова конвертируется в целое число).

источник

2014-01-15 19:30:53 tabstop

Внутренний контур выполняет вызовы 3 * i/2. Внешняя петля имеет i = n, n + 4, n + 8 .. 2n-4. Поэтому мы имеем:

count = 3*n/2 + 3*(n+4)/2 + 3*(n+8)/2 + ... 3*2*n/2 = 
= 3/2 * (n + (n+4) + (n+8) + .. + (2n-4)) = 
= 3/2 * (3n^2-4n)/8 = 
= (9n^2 - 12n)/16

(Edit: там может быть небольшие неточности, которые должны быть фиксированы)

Edit # 2 - я последовал самостоятельной «s коррекции, и теперь я получаю ожидаемый результат ,

источник

2014-01-15 19:33:20

Как вы получили '(n^2/4 + (4 + 8 + .. n))' from ' (n + (n + 4) + (n + 8) + .. + 2n) '? Это '(n^2)/4' или' n^(2/4) ' – this

Вы близки, но последние цифры неверны. Если вы запустите код, вы получите другой результат. – this

Действительная формула, которая работает, если n делится на 4, равна '(n/4) * ((9n/4) -3)'. – this

Ниже приведены формальные шаги, которые позволили бы вам вывести точное число раз function() будет выполнять:

Внешний цикл будет выполняться п + CEIL (п/4) - 1 раз, внутренний контур зависит от внешнего контура. Я попытался максимально подробно описать это решение.

источник

2014-03-25 07:22:11

Сколько раз функция будет вызываться?

ответ

Смежные вопросы