Как вложенный цикл, который имеет сложность O (n)?

Question

Дано:

for (int i = 1; i <= n;  i *= 2) {
  for (int j = 0; j < i; j++) {
    // Statement(s) that take(s) constant time
  }
}

Сложность времени выполнения = O(n)

Объяснение было:

Я понимаю, что внешнийцикл равен log(n), а внутренний цикл - O(n). Но почему сложность времени не O(n log n)? почему это O(n + log n)?

Answer 1

Внешний цикл запускается log(n) раз. Но каждый раз внутренний цикл не запускается в O(n). Как показано в объяснении, если i = 1, внутренний цикл запускается 1 времени. Если i = 2, внутренний цикл запускается 2 раза. Если i = 4, внутренний цикл запускается 4 раз. Следовательно, общее количество времени выполнения составляет T(n) = 1 + 2 + 4 + ... + 2^log(n).

Теперь упростим T(n):

T(n) = 2^(log(n)+1) - 1 = 2^log(n) * 2 - 1 = 2n - 1 = Theta(n)

Answer 2

Расчет частичных сумм правильный. Тем не менее, объяснение общего времени выполнения неясно, хотя результат действительно O(n). Фактическое время расходуется на выполнение внутренних операторов, а количество выполнений этих операторов определяется циклами. Метод частичных сумм уже учитывает оба цикла (1 единица времени для i = 1, 2 единицы времени для i = 2, 4 единицы времени для i = 4 и т. Д.) И в целом внутренняявыписки выполняются O(n) раза, как показано при расчете частичных сумм. Следовательно, общее время составляет O(n)*O(constant for the internal statements)=O(n). Я не вижу смысла включать O(logn) в расчеты здесь.