Oszacowanie złożoności obliczeniowej

0

Mam nietypowy program, gdyż jak z pisaniem nie mam problemów tak z oszacowaniem złożoności obliczeniowej ogromne:D a na zajęcia prowadzący wymaga tego i tego więc czy ktoś by mi mógł oszacować złożoność obliczeniową poniższego programu?:D prosze:D

program ma podawać minimalną ilość monet wykorzystaną do wydania podanej kwoty

int main()
{
    
    int max=2147483647; //jakaś duża liczba
    int k=36; //podana kwota
    int a=7; //ilość nominałów do wykorzystania
    int t[k];
    t[0]=0;
    int m[] = {1,2,5,7,10,13,20}; //tablica z wykorzystanymi nominałami
    
    for(int i=1;i<k;i++)
    {
            t[i]=max;
    }
    
    for(int i=0;i<a;i++)
    {
            int n=m[i];
            
            for(int j=0;j<=k-n;j++)
            {
                    if(t[j]<max)
                    {
                                if(t[j]+1<t[j+n])
                                {
                                                 t[j+n]= t[j]+1;
                                }
                    }
            }
    }
       
    cout<<t[k]<<endl;

    system("pause");
    return 0;
}
0

O(a*k), wg twoich oznaczeń.

0

O(k) właściwie bo a jest tutaj stałą ;)

0

Nie jest napisane że a jest stałą ;]

0

Założyłem ze skoro tablica nominałów jest statyczna to można uznać że jest ich stała ilość ;)
Może to moja nadinterpretacja :)

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