Сколько раз n может быть floor (sqrt (n)) - 1, а n> 0?

Question

Полный вопрос:

Предположим, у нас есть функция

void foo(int n){
  int i = n;
  while(i > 0){
    //do an O(n) operation
    //do some O(1) operations
    i = sqrt(i) - 1;
  }
}

Мне просто нужно найти асимптотические оценки, но я не могу этого сделать, пока не выясню, сколько разцикл на самом деле работает.Я предполагаю, что это еще одно суммирование с использованием квадратного корня, но я не знаю, с чего начать.

Answer 1

Вы хотите узнать, сколько раз цикл будет выполняться.

Если i <2, то цикл будет выполняться максимум дважды. </p>

Поэтому, если i <4, цикл будетвыполняется не более 3 раз. </p>

Поэтому, если i <16, цикл будет выполняться не более 4 раз. </p>

Поэтому, если i <256, цикл будет выполняться не более 5 раз. </p>

...

и т. Д.

Вы видите, что если i <2 ^ (2 ^ m), то цикл будет выполняться максимально (m + 2) раза. </p>

Это означает, что порядок того, сколько раз он будет выполняться, равен log (log (n)),

, поскольку i начинается с n.

Таким образом, общая сложность составляет O(n*log(log(n)).

(Это если число операций O (1) в каждой итерации является постоянным.)

Answer 2

То же O (n log log n), что и у Petar, но вот некоторые более четкие границы.Если i = floor (sqrt (i)) -1,

, если n <1, цикл равен нулюесли n <2², то цикл не более 1 разаесли n <(2 ² +1) ² = 5 ², оно повторяется не более 2 разесли n <(5 ² +1) ² = 26 ², цикл повторяется не более 3 разесли n <(26 ² +1) ² = 677 ², он повторяется не более 4 раз </p>

Согласно Онлайн-энциклопедии целочисленных последовательностей , этой последовательности (1, 2, 5,26, 677, ...) асимптотически относительно 1,22 ^ (2 ^ k) [а также k-е число представляет число бинарных деревьев высотой не более k].Таким образом, для числа n число циклов равно O (log log n), а ваш алгоритм - O (n log log n).