[Teoria złożoności][Python] Programowanie dynamiczne

[Hendra]

Witajcie!
Chciałbym policzyć złożoność czasową poniższego algorytmu, ale nie jestem pewien czy zrobiłem to dobrze. Bardzo prosiłbym o ewentualne korekty.
Algorytm:

Kod: Zaznacz cały

def ilość_1(C):
    a = list(set(map(int, input().split())))

    dp = [[0 for _ in range(len(a))] for __ in range(C + 1)]
    dp[0][0] = 1

    for i in range(C):
        for j in range(len(a)):
            for k in range(j, len(a)):
                if i + a[k] <= C:
                    dp[i + a[k]][k] += dp[i][j]

    return sum(dp[C])

Z moich wyliczeń wyszła mi złożoność: \(\displaystyle{ len(a)^{2} \cdot C + len(a) \cdot (C+1)}\)

[bartek118]

To zależy, jakie operacje zliczasz. Ten pierwszy składnik jest jedynie górnym oszacowaniem liczby przebiegów tych zagnieżdżonych pętli. Można to policzyć dokładniej.

[Hendra]

To zależy, jakie operacje zliczasz. Ten pierwszy składnik jest jedynie górnym oszacowaniem liczby przebiegów tych zagnieżdżonych pętli. Można to policzyć dokładniej.

To prawda, ale na tamtym etapie jeszcze o tym nie wiedziałem
Teraz wyszło mi coś takiego:
\(\displaystyle{ T_{1}+T_{2}+T_{4}+T_{8}+T_{10}+(len(a)+C+3)T_{3}+(C+1)T_{5}+(len(a)+1)T_{6}+\Bigl(\frac{1}{2}len(a)^{2}+3len(a)\Bigr)T_{7}+\frac{1}{2}(len(a)^{2}+len(a))T_{9}}\)
Przy czym indeksy odnoszą się do poszczególnych linijek kodu (liczone od 1, puste linijki pominąłem).
Czy teraz jest ok?
Jak to się ma do złożoności kwadratowej? Bo mam tutaj \(\displaystyle{ len(a)}\) i \(\displaystyle{ C}\).

[bartek118]

Nadal nie podałeś, jakie operacje zliczamy.