Биг-О:Почему временная сложность этих циклов O(N)?
-
29-09-2020 - |
Вопрос
У меня есть следующая функция.
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
В нем есть O(N)
временная сложность.Я думал, что это O(N LogN)
(т.е.Если убрать внутренний цикл, то получим)
for (int i = n; i > 0; i /= 2){
...
}
Это O(Log N)
не так ли?И внутренний цикл оказывается O(N)
поскольку он просто увеличивается линейно.Так что я думаю, что так и должно быть O(Log N * N)
.Что может пойти не так в моей мысли?
Решение
Посмотрите, сколько шагов делает внутренний цикл.Его $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$.Однако геометрическая серия говорит нам:
$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^к} = 2n$$
Не связан с cs.stackexchange