for(i = 1; i < n; i *= 2) {
sum++;
for(j = 0; j < n; j += 2)
total++;
}
Временная сложность:Временная сложность логарифмическая
O(log(n))
O(log(n))
O(n)*O(log(n))
O(n)*O(log(n))
Так окончательный ответ: O(log(n))
Правильно ли это?
сложность будет что-то вроде этого:
O(lgN)
O(1)
O(N/2) == O(N)
O(1)
поэтому сложность:
это окончательный ответ O (ЛГН) * (O (1) + O (N) * O (1))
O (N) * O (1) = O (N) (1)
O (N) + O (1) = O (N) (2) из-за вывода (N) больше, чем O (1)
в предположении (1) & (2) окончательный ответ будет O (ЛГН) * O (N) = O (N ЛГН)
ohh сумма ++ не является O (logn), потому что я подразумеваю ее внутри цикла –
Да, но почему if его не вложенный ответ O (n) не O (log (n))? –
, когда вы вычисляете сложность n/2, равно n, n + 3 равно n, ... –
Сложность: О (п) * O (LG (n))
Ваш код не ясен, сначала напишите его в форме, в которой мы можем узнать, какая инструкция предназначена для? является вторым для вложенного цикла? –
Да, это вложенная петля –
По этому коду нет, это не –