Как рассчитать временную сложность биг-тэты во фрагментах кода?

Question

Я выполняю упражнение по анализу сложности времени для фрагментов кода, однако мне трудно понять, как следующие два кода могут иметь различную сложность времени:

for(a=1,a<=n,a++):
 for(b=1,b<=a, b++):
   c=c+1

Какое время выполнениякода можно выразить как θ (n ^ 2).

Тем не менее,

for(a=1,a<=n,a=2*a):
 for(b=1,b<=a, b++):
   c=c+1

выражается как θ (n).

Я думал, что вторые фрагментыкода имеет время выполнения θ (n ^ 2/2) = θ (n ^ 2).Видимо я ошибся.Не могли бы вы дать несколько советов, как правильно проанализировать временную сложность упомянутых двух кодов?Это очень поможет, спасибо.

Answer 1

Вы увидите это ясно, когда развернете их.Позвольте мне попробовать:

Первый фрагмент: предположим, что n = 8

a = 1, b = 1
a = 2, b = 1,2
a = 3, b = 1,2,3
a = 4, b = 1,2,3,4
a = 5, b = 1,2,3,4,5
a = 6, b = 1,2,3,4,5,6
a = 7, b = 1,2,3,4,5,6,7
a = 8, b = 1,2,3,4,5,6,7,8

Второй фрагмент: предположим, что n = 8

a = 1, b = 1
a = 2, b = 1,2
a = 4, b = 1,2,3,4
a = 8, b = 1,2,3,4,5,6,7,8

Простым подсчетом числа циклов выше, вы начнете видеть, что a=a*2 отменил число внешних циклов в той же пропорции.

На самом деле, я считаю, что ответ должен быть θ(n log(n))

Надеюсь, что это поможет.