int n;
int i, j, k = 0;
for (i = n/2; i <= n; i++) {
for (j = 2; j <= n; j = j * 2) {
k = k + n/2;
}
}
Просто нужно вычислить временную сложность фрагмента кода, и ответ Θ (NlogN), но вы можете объяснить, как это Θ (NlogN)Какова временная сложность кода Θ (nLogn)?
Это действительно не так сложно.
Наружный контур работает n/2 раз. То есть O(n) сложность.
Внутренний цикл снова зависит только от n. Это не зависит от i от первого цикла. Поэтому для сложности внутреннего цикла мы можем полностью игнорировать внешний цикл. Как повезло !. j умножается каждый раз на 2 поэтому у нас есть logarithm base 2. Это O(log(n)).
петли вложены таким образом, мы умножаем, таким образом, заканчивая:
O(n log(n))
Таким образом, вы имеете всю информацию. Почему вы не можете рассчитать? –
Ваш намек на то, что это не O (n!). Если серьезно, если вы не можете понять это через экзамен, поместите там несколько вызовов printf, чтобы узнать, как часто это называется, и посмотрите, не можете ли вы сами найти шаблон, когда вы меняете размер петли? –
«... можете ли вы объяснить, как это Θ (nLogn)» - можете ли вы объяснить, как это могло быть что угодно, но * Θ (nLogn)? – WhozCraig