Największa suma - pseudokod

0

Mam o to taki pseudokod, który liczy największą sumę spójnych elementów w danym ciągu:)

 MAKSYMALNA SUMA (A,n)
suma -> 0
dotądNaj -> 0
    for i <- 1 to n
        if (suma > -A[i]) then
            suma <- suma + A[i]
        else
            suma <- 0
        endif
        dotądNaj <- MAX (dotądNaj, suma)
return dotądNaj 

W tym algorytmie jest jedna pętla o stałej długości = n, brak pętli zagnieżdżonych, czyli wnętrze pętli jest O(1), a n*O(1) = O(n) - złożoność obliczeniowa tego algorytmu. Teraz rodzi się pytanie jak to ładnie zapisać matematycznie? Dać dowód na to, że jest taka złożoność:)

Ktoś pomoże?

0

Skoro pętla wykona się n + 1 razy, to ilość wykonań tej pętli to n + 1.

Jako, że n + 1 < 2n dla n > 1, to złożoność asymptotyczna tej pętli to O(n), a nawet theta(n), bo pętla wykona się tyle samo razy w każdym przypadku.

W pętli jest jakaś stała liczba operacji, oznaczmy ją C, jako że n + 1 + C < 2n dla n > d, gdzie d oznacza liczbę dla których funkcja 2n jest większa od n + 1 + C, gdzie C jest stałą, więc n + 1 + C = O(n).

Poza tematem pisz ładniejsze pseudokody. Zastrzeżenia:

  1. W warunku piszesz <-, zamiast <=, jak się przyjęło w większości języków programowania i pseudokodów. Dodatkowo tak samo zapisujesz przypisanie, przez co te dwie operacje mylą się gdy się czyta kod. Do tego warunek (suma > -A[i]), a jakbyś miał zapisać >=, to co? Wtedy wyglądało by to tak (suma >- -A[i]). Bardzo brzydko - łatwo można się pomylić.

  2. Po suma := 0 piszesz end, a gdzie był begin, czy inny nawias rozpoczynający?

  3. Co znaczy endif?

Zanim wstawisz następnym razem kod na forum, zadbaj wcześniej o czytelność.

0

mam w ramach zajec przerobic pewien algorytm w pseudokodzie i w takim samym pseudokodzie zapisac.
Endif - oznacza koniec operacji warunkowej:)

 MAKSYMALNA SUMA (A,n) 
 dotądNaj <- 0 
 for d <- 1 to n 
    do suma <- 0 
       for g <- d to n 
          do suma <- suma + A[g] 
             dotąd naj <- MAX (dotądNaj, suma) 
 return dotądNaj
0

do suma < -suma+A[g] to pętla? :)

MaksymalnaSuma (A, n)
    dotądNaj := 0
    for d:= 1 .. n
        suma:= 0
        for g:= d .. n
            suma:= suma + A[g]
            dotądNaj:= MAX( dotądNaj, suma )
    return dotądNaj

MAKSYMALNA_SUMA (A,n)
    suma := 0
    dotądNaj := 0
        for i := 1 .. n
                //if suma > -A[i]
                //        suma := suma + A[i]
                //else
                //        suma := 0
                suma:= MAX( suma + A[i], 0 );

                dotądNaj := MAX ( dotądNaj, suma )
    return dotądNaj
0

a czemu pętla się wykona n+1 a nie n razy?

0

Pętla się wykona n + 1 razy, ponieważ przy n + pierwszym sprawdzeniu warunku pętla przyjmuje wartość logiczną false.

Pętla for i := 1 to n zawsze wykonuje się n + 1 razy, ponieważ to nie jest tak, że jakoś jest odmierzana wartość i do końca (tak błędnie mogą sobie niektórzy wyobrażać), tylko za każdym razem jest sprawdzany warunek.

Dla n = 2 pętla przyjmie wartość true dla i = 1 i i = 2. Następnie warunek sprawdzany jest jeszcze raz, dla i = 3 i wtedy mamy już wartość false. Mamy 2 + 1 razy, czyli n + 1 razy.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0