Сколько раз x = x + 1 выполняется в тета-нотации в терминах n?

Question

Я беру анализ данных и алгоритмы летом.

Вопрос: Найти Θ-обозначение в терминах n для количества раз, когда выполняется инструкция x = x + 1.

for i = 1 to 526 
    for j = 1 to n^2(lgn)^3 
     for k = 1 to n 
      x=x+1 

Я смущен тем, как найти ответ. Первая строка будет 526, тогда вторая строка будет явно n^2 раза (lgn)^3, но это может быть 3 (n^2) lgn? И тогда третья строка - это просто n. Таким образом, они были бы объединены в 526 * n^3 (lgn)^3, и только с n это было бы что-то вроде Θ (n^3) (lgn)^3. Я не уверен.

Кроме того, чтобы убедиться, что я понимаю, такого рода проблемы у меня есть

for i = 1 to |nlgn| 
    for j = 1 to i 
     x=x+1 

Ответ будет просто nlgn, потому что я на второй линии не важно?

Answer 1

Ответ на первой части: -

for i = 1 to 526 
for j = 1 to n^2(lgn)^3 
    for k = 1 to n 
     x=x+1 

Эта программа будет работать 526 * п^2 * (Л.Г. п)^3 * п раз = 526 * п^3 * (Л.Г. n)^3 раза.

Итак, x = x +1 будет выполнено 526 * n^3 * (lg n)^3 раза.

Далее в Большой-тета нотации,

В п всегда больше, чем (LG п) для любого п> 1, так что,

c1 * n^3 <= 526 * n^3 * (lg n)^3 <= c2 * n^3 * (lg n)^3 

для некоторых положительных констант c1 < 526 и с2> 526, поэтому обозначение большой тета будет

θ (n^3 * (lg n)^3).

Ответ на второй части,

for i = 1 to |nlgn| 
for j = 1 to i 
    x=x+1 

Ваше предположение совершенно неправильно. Внутренняя петля, управляемая j, также необходима для оценки выражения x = x + 1, поскольку она является телом внутреннего цикла, который сам является телом внешнего цикла.

Итак, вот, х = х + 1 будет оцениваться для

= 1 + 2 + ... + n*(lg(n) times 
= [n*lg(n) * {n*lg(n)}+1]/2 times. 

Answer 2

Ответ на втором примере не NlogN. Вы не можете просто умножить границы двух для петель друг к другу. Второй цикл формирует сигму, поскольку второй цикл перемещается от 1 до i, который может быть не более nlogn. Эта сигма будет 1 + 2 + ... + nlogn ... Суммирование этой сигмы можно найти по формуле суммы натуральных чисел. Поэтому сигма есть (nlogn * (nlogn + 1))/2.