Сигма Нотация в анализе L oop - PullRequest
Новая
       37

Сигма Нотация в анализе L oop

1 голос
/ 29 января 2020

Наш профессор предоставил несколько раздаточных материалов, чтобы помочь с нашей домашней работой в моем классе «Алгоритмы и структуры данных».

Первый - обзор некоторых сигма-нотаций и связанных свойств. Это, конечно, списки:

\ sum_ {i = 1} ^ {n} c = cn

и

\ sum_ {i = 0} ^ {n} c = c (n + 1)

В другом раздаточном материале были примеры того, как использовать сигма-нотацию для подсчета количества операций в al oop.

В этом раздаточном материале указан псевдокод:

"для меня. \ LeftArrow От 1 до n делать: "

будет переводиться в

1 + (\ sum_ {i = 0} ^ {n + 1} 1) = (n + 2) +1 = n + 3

Я понимаю 1 операцию по инициализации l oop (1+), но почему, черт возьми, мы внезапно суммируем n + 1? Разве мы не суммировали бы от 0 до n с результатом

1 + (\ sum_ {i = 0} ^ {n} 1) = 1 (n + 1) +1 = n + 2

Я также написал профессору и ТА по электронной почте, но оба они были менее чем полезны. Итак, любая дополнительная информация, которая может быть предоставлена, будет принята с благодарностью. Это одна вещь, которая действительно держит меня, и это очень расстраивает. Я имею в виду, я сумасшедший? Или записи не так?

РЕДАКТИРОВАТЬ: мои извинения; У меня было "для 0 <- 1 до n, делай:". Должно быть написано «для i <- 1 to n do:» </p>

Ответы [ 2 ]

1 голос
/ 29 января 2020

Как вы выходите из l oop? Вы увеличиваете значение до n+1, проверяете условие и затем выходите.

Это может помочь рассмотреть конкретное значение 3 для n. Вот операции. 

set i to 0
set i to i+1 (1) and test whether i (1) is > n (3)
set i to i+1 (2) and test whether i (2) is > n (3)
set i to i+1 (3) and test whether i (3) is > n (3)
set i to i+1 (4) and test whether i (4) is > n (3)

И теперь вы видите, что 1 для инициализации, и есть 4 попытки увеличения, прежде чем вы закончите цикл.

Тело l oop будет, конечно, также n+1 раз.

0 голосов
/ 01 февраля 2020

Мой TA, наконец, предоставил поучительный ответ:

Когда псевдокод говорит «для i <- 1 до n do:» </p>

Это было бы эквивалентно записи a для l oop такой, что: 

for (i = 1; i <= n; i++);

В этом случае мы рассчитываем сравнения i<=n , включая n . Таким образом, l oop завершится после n + 1 сравнений. N + 1-е сравнение является условием выхода. Следовательно, мы получаем:

\ Sum_ {I = 1} ^ {п + 1} 1

Аналогично, если псевдокод читает «для i <-1 - n-1 do», это будет эквивалентно: </p> 

for (i = 1; i < n; i++);

Итак, мы выполним сравнения i<n up до , но НЕ включая n . Девятое сравнение будет условием выхода. Итак, мы бы получили:

\ Sum_ {I = 1} ^ {п} 1

Я думаю, что это в значительной степени то, что говорили большинство из вас, мне просто было трудно обдумать это без реального code примера того, что говорил псевдокод. Я не знаю, является ли это соглашением для всех классов анализа алгоритмов или только для нас. Но я хочу поблагодарить всех за помощь!

...