Рассмотрим этот фрагмент кода
int sum = 0;
for( int i = 1; i <= n*n; i = i*2 ){
sum++ ;
}
Как сделать быстрый правильный анализ, чтобы получить порядок роста времени работы в худшем случае?
Как изменение оператора приращения на i = i * 3 вместо i = i * 2 меняет время работы в наихудшем случае?
И влияет ли на наш анализ изменение оператора сравнения на < вместо <=?
int sum = 0;
for( int i = 0; i <= n*n; i = i*2 ){
sum++ ;
}
В нынешнем виде это бесконечный цикл, который никогда не остановится, поскольку i никогда не меняется. Поскольку сложность определена только для алгоритмов, которые по определению должны завершаться за конечное время, для этого фрагмента она не определена.
Однако, если вы измените код на следующий:
int sum = 0;
for( int i = 1; i <= n*n; i = i*2 ){
sum++ ;
}
Мы можем проанализировать сложность следующим образом:
Пусть цикл выполняется k - 1 раза и завершается при kth обновлении i. Поскольку лучше быть избыточным, чем неясным, вот что происходит:
Init(1) -> test(1) -> Loop(1) [i = 1]->
Update(2) -> test(2) -> Loop(2) [i = 2]->< br> ...
Update(k - 1) -> test(k - 1) -> Loop(k - 1) [i = 2 ^ (k - 2)] ->
Update(k) -> test(k)->STOP [Тест не пройден, так как i становится 2 ^ (k - 1)]
Где Update(k) означает kth обновление (i = i * 2).
Поскольку приращения в i таковы, что в цикле pth (или, что то же самое, после pth updation) значение i будет 2 ^ (p - 1), мы можем сказать, что при завершении:
2 ^ (k - 1) > (n * n)
Если говорить подробно, мы остановились на k-м обновлении. Каким бы ни было значение i, оно было бы больше (n * n), иначе мы бы зациклились на kth. Принимая log base 2 с обеих сторон:
k ~ 2 * log(n)
Это означает, что k равно O(log(n)).
Соответственно, цикл выполняется O(log(n)) раз.
Вы можете легко расширить эту идею до любого предела (скажем, n*n*n) и любых приращений (i*3, i*4 и т. д.).
На сложность Big O не повлияет использование < вместо <=
На самом деле этот цикл является бесконечным циклом.
i=0
i=i*2 //0*2=0
Так что эта петля никогда не закончится. Сделайте i=1, чтобы получить количество степеней от 2 до n^2, а не суммы.
для любого цикла, чтобы проанализировать его. Вы должны увидеть 2 вещи. условие, которое заставит его выйти, и итерация, применяемая к переменной, используемой в условии.
для вашего кода. Вы можете заметить, что цикл останавливается, когда i переходит от 0 к n * n (n ^ 2). и переменная i увеличивается как i = i*2. поскольку i увеличивает i таким образом, цикл будет выполняться log (n ^ 2) раз. это вы можете увидеть, взяв пример значения n ^ 2, например 128, а затем повторяя его вручную один за другим.
