Mam taki algorytm i nie bardzo wiem jak zapisać jego złożoność uwzględniając wszystkie operacje w pętli, ale używając symbolu sumy - sigmy. Jest to algorytm znajdowania największej sumy w tablicy A[].
Ja liczyłem złożoność tego algorytmu tak na logikę: operacja w linii 1, 2 i 9 wykona się tylko raz, a pętla w linii 3 i operacje w liniach 4, 5 i 6 wykonają się tyle razy co pętla czyli n, więc dokładna złożoność to: 4n+3. O-notacja pomija stałe i wyrazy niższego rzędu więc złożoność O(n).
1. dotądNaj = 0
2. suma = 0
3. for i = 1 to n{
4. suma = suma + A[i]
5. suma = max(0,suma)
6. dotądNaj = max(dotądNaj,suma)
7. }
8. }
9. return dotądNaj
Jeżeli ktoś potrafi to bardzo proszę żeby pokazał mi jak coś takiego się zapisuje Sumą z uwzględnieniem wszystkich operacji.
To podobno jest przykład z literatury więc jeżeli ktoś wie gdzie to zostało opisane to bardzo proszę o informację.
Z góry dziękuję