Выяснение сложности программы при использовании цикла while

Question

Какова будет сложность времени для следующего кода?

int fun1(int n) {
  int i = 1;
  int count = 0;

  while (i < n) {
    count++;
    i = i * 2;
  }

  printf("Loop ran %d times\n", count);

  return 0;
}

Answer 1

Все предложения O (1), а l oop записывает (n) (основание 2) итераций, так как i удваивается (i=i*2) на каждой итерации, поэтому ее log (n) (основание 2) ,

Вы можете найти больше информации здесь Какова временная сложность циклов while? .

Answer 2

Временная сложность вышеуказанного кода: O(log(n))

int fun1(int n) {
  int i = 1;
  int count = 0;

  // Here i runs from 1 to n 
  // but i doubles every time
  // i = 1 2 4 8 16 .... n
  // Hence O(log(n))
  while (i < n) {
    count++;
    i = i * 2;
  }

  printf("Loop ran %d times\n", count);

  return 0;
}

Предположим, n = 16 == 2^4

В этом случае l oop будет работать только 4 раза == 1 2 4 8 == log(16)

Answer 3

Посмотрите на эту часть вашего кода:

  while (i < n) {
    count++;
    i = i * 2;
  }

i умножается на 2 на каждой итерации.

Первоначально i равно 1.
Итерация I:
i = 1 * 2; => i = 2
Итерация II:
i = 2 * 2; => i = 4
Итерация III:
i = 4 * 2; => i = 8
Итерация IV:
i = 8 * 2; => i = 16
.....
.....
и т. Д.

Предполагается n это число, которое равно 2 ^k . Это означает, что l oop будет выполнено k раз. В k ^th шаг:

2 ^k = n

Взятие логарифмов (основание 2) с обеих сторон:

log (2 ^k ) = log (n)

k log (2) = log (n)

k = log (n) [as log2 (база 2) = 1]

Следовательно, сложность времени равна O (log (n)).