Для цикла с сложностью реализатора умножения

Question

for(int i=1; i<n; i=2*i)
// simple addition performed here...

Я понимаю, что O (n) одно время выполнения для циклов и O (n ^ 2) вложено для циклов, но является ли время выполнения в этом цикле также n log n с момента умножения?

Спасибо,

Answer 1

Нет, вы правы, что здесь происходит умножение, но оно служит для уменьшения добавленного времени выполнения, а не для увеличения этого.

Вы должны посмотреть, как быстро заканчивается цикл, основываясь на входном значении n. За n = 128 вы получите i = 1, 2, 4, 8, 16, 32, 64, 128. Если вы удвоите n, это не удвоит время, как это было бы для O (n), и, конечно, не умножит его на 4, как это было бы для O (n ² ). Он просто добавляет еще одну итерацию в цикл.

Это то, что известно как временная сложность O (log N). Время выполнения увеличивается с логарифмом входного значения, и это обычно наблюдается в вещах типа сбалансированного двоичного дерева, где вы можете удалить половину оставшегося пространства поиска с каждой итерацией.

Answer 2

Как утверждает @paxdiablo, это цикл O (log n)

O (n log n) будет

for(int i=0;i<n;i++) 
   for(int j=i;j>0;j/=2)

Когда есть вложенный цикл O (n) и O (log n)