Określenie zlożoności czasowej algorytmu

0

Witam,
Chciałabym prosić o pomoc w ustaleniu, czy algorytm ma złożoność czasową lepszą bądź gorszą od kwadratowej. Wiem, że jest to prymitywnie napisane,ale dopiero niedawno zaczęłam przygodę z programowaniem.
Kod:

def kasa(C):

    raz = 0
    dwa = 0
    pięć = 0
    dziesięć = 0
    dwadzieścia = 0
    pięćdziesiąt = 0
    wyniki = []
    if C == 0:
        return None 
    if C > 4:
        wyniki += parzyste_1(C)
    while C >= 50:
        C = C - 50
        pięćdziesiąt +=1
    while C >= 20:
        C = C - 20
        dwadzieścia +=1
    while C >= 10:
        C = C - 10
        dziesięć += 1
    while C >= 5:
        C = C-5
        pięć += 1
    while C >= 2:
        C = C - 2
        dwa += 1
    while C >= 1:
        C = C - 1
        raz += 1
    wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    while pięćdziesiąt >= 1:
        pięćdziesiąt -= 1
        dwadzieścia += 2
        dziesięć +=1
        wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    while dwadzieścia >= 1:
        dwadzieścia -= 1
        dziesięć += 2
        wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    while dziesięć >= 1:
        dziesięć -= 1
        pięć += 2
        wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    while pięć >= 1:
        pięć -= 1
        dwa += 2
        raz += 1
        wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    while dwa >= 1:
        dwa -= 1
        raz += 2
        wyniki += raz,dwa,pięć,dziesięć,dwadzieścia,pięćdziesiąt
    return len(wyniki)//6
2

To ma niby wyliczać na ile sposobów można wydać daną kwotę? o_O Jeśli tak to brak mi słów, bo wyszło mega skomplikowane, podczas gdy ten problem można rozwiązać jedną pętlą w czasie liniowym względem kwoty do wydania. Zastanów się nad zrobieniem tego dynamicznie korzystając z własności optymalnej podstruktury. Tzn zauważ że wiedząc na ile sposobów można wydać kwotę k, łatwo wyliczyć na ile sposobów można wydać kwotę k+1.
Twój alogorytm nie ma jak się zdegradować do O(n^2) ale masz bardzo dużo niepotrzebnych liniowych przejść i pesymistycznie jest O(n*k) gdzie k to liczba dostępnych nominałów.

2

Zakładając, że wykonanie parzyste_1(C) ma złożoność O(1):

  1. Pierwszy if — O(1).
  2. Pierwsza wiązanka while’i — wykona się w najlepszym przypadku n/50 razy, w najgorszym n razy, więc O(n).
  3. Każdy z kolejnych while’i także wykona się nie więcej niż n razy.

Złożoność masz więc liniową.

Oprócz tego, polecam zapoznać się z operatorami // oraz %, bo po co mieć pętle (i złożoność liniową) tam, gdzie wystarczy jedna operacja (więc złożoność stała).

0

Bardzo dziękuję za odpowiedzi.
Zamierzam teraz zmienić ten kod, muszę go jeszcze uzależnić od N - zbioru nominałów. Jednak nie wiem,w jaki sposób to zapisać, aby porównać kwotę(C) z kolejnymi elementami zbioru N ;/
Chyba najlepiej byłoby zacząć to zadanie od nowa. Czytałam wcześniej o programowaniu dynamicznym, ale nie mam pojęcia od czego zacząć i jak zaimplementować to w taki sposób. Będę wdzięczna za jakąkolwiek wskazówkę

0

No bez przesady, jesteś matematyczką a ten "algorytm dynamiczny" tutaj to nic innego jak zastosowanie indukcji matematycznej. Zacznij od tego o czym napisałem wyżej. Wiedząc na ile sposobów można wydać kwoty do 1 do X, jak policzysz na ile sposobów wydać kwotę X+1? Załóż że masz tablicę tab gdzie tab[i] to liczba sposobów na ile można wydać kwotę i.

0

Znowu mam problem z określeniem złożoności.
Po zmianie funkcja jest zależna od N - listy nominałów. W pętli for jest to O(ilość nominałów), czy jest to zatem O(n), czy gorsza?

0

Ale w jakiej pętli? Pokaż algorytm o który pytasz.

0
def kasa(C,N):

    x = [1]+[0]*C
    if C < 0:
        return 0
    if N == []:
        return 0 
    for N in N:
        for i in range(N,C+1):
            x[i]+=x[i-N]
    return (x[C])

Próbowałam to rozpisać:

  1. if - O(1)
  2. Pierwszy for - O(ilość N) czyli O(n) ?
  3. Drugi for - O(C+1-N) czyli O(n)
  4. Łącznie 2. i 3. (for w for) - O(n^2)
1

for N in N: to chyba nie zadziała ;)
Dużo czytelniej byłoby iterować w pierwszej pętli po kwocie tak btw, no ale jak tam sobie chcesz.
Niemniej jednak za bardzo kombinujesz w obliczeniach. Masz pętle zewnętrzną kręcącą się N razy (czyli tyle ile jest nominałów) a dla każdego nominału pętla wewnętrzna kręci się C-i razy, ale generalnie wiemy że w przypadku ogólnym nominały są mniejsze od kwoty do wydania więc C-i ~= C, więc ta pętla kręci się O(C) razy. W efekcie złożoność całośi wynosi oczywiście O(N*C). Jeśli dodatkowo założymy że liczba nominałów jest stała lub bardzo mała to algorytm będzie liniowy względem kwoty czyli O(C) zgodnie z twoimi oznaczeniami.

Nie wiem czym dla ciebie byłoby O(n) czy też O(n^2) skoro w algorytmie nie ma zadnego n.

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