Блог

Главная - Вопросы по программированию - Асимптотическая сложность для алгоритма

Асимптотическая сложность для алгоритма

#big-o #complexity-theory #time-complexity #pseudocode

#большой o #сложность-теория #временная сложность #псевдокод

Вопрос:

 i <-- 0
while(i < n)  
    someWork(...)
    i <-- i^2
done

Может ли кто-нибудь подтвердить, что временная сложность наихудшего случая (Big-O) этого цикла равна O(log n) , если:

  1. someWork(...) является O(1) алгоритмом

  2. someWork(...) является O(n) алгоритмом

Кроме того, какова временная сложность наихудшего случая (Big-O), если someWork(...) выполняются точные i операции? someWork(...) выполняет больше работы по мере i увеличения. Ваш ответ должен быть чем-то вроде sigma(f (i)).

Большое вам спасибо за любую помощь.

Комментарии:

1. На самом деле, это бесконечный цикл, который i всегда будет оставаться 0 .

2. Если вы исправите, как предложил Дон Робби, т. Е. добавите что-то, о чем нужно позаботиться, когда n < 2 и инициализируете i = 2 (или любое число > 2, но меньше n). 1. Некоторая работа равна O (1), тогда это O (log n) 2. Некоторая работа равна O (n), тогда это O (n log n) Если некоторая работа выполняется в O (i), тогда O ((log n) pow x) где x равно либо 1, либо 2.

3. Спасибо за ответы на данный момент, вам обоим. Итак, правильно ли я буду рассуждать о том, что большого O нет, потому что программа никогда не завершается во всех трех ситуациях?

Ответ №1:

Первое: если (как упоминалось) 0 <= i <= 1 выполняется, алгоритм никогда не завершится.

Итак: Пусть i > 1 .

В каждом раунде цикла показатель i будет удваиваться. Итак, в k -м раунде число будет i^(2^k) . Цикл продолжается до тех пор, пока i^(2^k) < n выполняется, что эквивалентно k < log log n . Именно так оно и есть log_2 log_i n , но из-за того, что все логарифмы равны, за исключением постоянного множителя, я просто пишу log log n . Обратите внимание: if i не является постоянным, 1/log log i должно быть умножено на сложность.

Таким образом, сложность алгоритма равна

  1. O(log log n) , если someWork() находится в O(1)
  2. O(n log log n) , если someWork() находится в O(n)

Если someWork() выполнять O(i^(2^k)) операции в раунде k , вы получите общую сложность

 O( i   i^2   i^(2^2)   i^(2^3)   ...   i^(2^(log log n)) )

Это упрощается до O(i * i^(2^(log log n)) ) = O(i * n) или O(n) , если i является постоянным.

Чтобы увидеть упрощение, взгляните на следующее:
Число i i^2 i^4 i^8 может быть записано i -арно как 100 010 110 . Итак, вы можете видеть, что

 i   i^(2^1)   i^(2^2)   ...   i^(2^k) < i * i^(2^k)

выполняется, поскольку оно равно 100 010 110 < 1 000 000 000 .

Редактировать:
я не уверен, что вы подразумеваете под сигма-обозначением, но, возможно, это так:
введите описание изображения здесь