Временные сложности заданных циклов O (logn) или O (n)

Question

//loop1
for (int i = 1; i <= n; i*=2) { }
//loop2
for (int i = 1; i <= logn; i++) { }

Мы спорим с моим другом о петлях, которые, я думаю, первая - O(logn), а последняя - O(n). Однако, для последнего он говорит, что это также O(logn) не O(n).

Не могли бы вы объяснить?

Answer 1

Если есть сомнения, просто замените значения n на некоторые значения и выполните оба цикла в пробном режиме.

Давайте возьмем n = 100 например.

// loop1

для (int i = 1; i <= n; i * = 2) {} </p>

Шаги (в форме i,n):

• 1, 100
• 2, 100
• 4, 100
• 8, 100
• 16, 100
• 32, 100
• 64, 100
• 128, 100

Технически, это решает в 7 шагах.

// loop2

для (int i = 1; i <= logn; i ++) {} </p>

• log ₂ (100) = 6,64 ~ 7.
• Шаги (в форме i,n):
  • 1, 7
  • 2, 7
  • 3, 7
  • 4, 7
  • 5, 7
  • 6, 7
  • 7, 7
  • 8, 7

Это также решается в 7 шагах. Следовательно, оба подхода имеют одинаковую сложность: O (log (n)).

Answer 2

Краткий ответ:

Оба имеют значение Log (n), поскольку для входа n оба цикла будут выполняться в течение Log (n) раз.

Пока первый цикл выполняется Log (n) раз из-за i *= 2 в цикле for, второй цикл запускается Log (n) раз из-за верхнего предела в цикле for, установленном непосредственно на это значение.

---

Подробно:

Big-O сообщает Скорость роста функции. Второй цикл - тот, который вас смущает - на самом деле проще из двух циклов. Вы можете непосредственно видеть, что для любого входа n функция всегда будет занимать время, пропорциональное только Log (n) .

Следовательно, скорость роста второго цикла пропорциональна Log (n) или, другими словами, равна O (Log (n)).