Домашнее задание: как рассчитать временную сложность этой функции? - PullRequest
Новая
       71

Домашнее задание: как рассчитать временную сложность этой функции?

0 голосов
/ 14 марта 2020 
void func(int n){
    int i=1, k=n;
    while (i<=k){
        k=k/2;
        i = i*2;
    }
}

Как рассчитать временную сложность этой функции? Я понимаю, что для присвоения i = 1, k = n требуется два базовых шага c, а для деления значения k и умножения значения i также требуется два базовых шага c, но поскольку значения i и k увеличиваются и уменьшаются в геометрической прогрессии, будет ли сложность времени O (логическая база 4 N) или O (логическая база 2 sqrt (N))?

1 Ответ

2 голосов
/ 14 марта 2020

Ваш ответ O (log √n), в комментариях @Eraklon говорит, что это O ((log 2 n) / 2), а @ matri70boss говорит, что это O (log 4 н). Вы все трое правы, но в простейшей форме ответ O (log n).

  • log √n = log n 0.5 = 0.5 log n, и мы отбросим постоянный коэффициент 0,5, когда мы пишем в больших обозначениях О.
  • (log 2 n) / 2 = (log n) / (2 log 2) путем изменения базовая идентичность , а 1 / (2 log 2) - еще один постоянный фактор, который мы можем отбросить.
  • Аналогично, log 4 n = (log n) / (log 4), и мы можем отбросить постоянный коэффициент 1 / (журнал 4).
...