Dec C: Unikke værdier

Best-/worst-case tidskompleksitet for find_unique, og Big O med set.

Den følgende funktion tager som input en liste, values, og returnerer en liste med de unikke værdier:

def find_unique(values):
    unique_values = []
    for x in values:
        if not x in unique_values:
            unique_values.append(x)
    return unique_values

Hver sammenligning og hver tilføjelse til en liste tæller som 1 operation, og længden af listen values er $n$. Tidskompleksiteten af x not in unique_values er $k$ (længden af unique_values), og unique_values.append(x) koster 1.

Spørgsmål C.1

Hvad skal gælde for listen values for at opnå et best-case tilfælde, og hvad er best-case tidskompleksiteten $T(n)$ målt i antal operationer?

Vis svar Skjul svar

Svar C.1

Best-case opnås når alle værdier er identiske, så unique_values får længde $k=1$.

Første værdi: 0 sammenligninger + 1 append. De resterende $n-1$ værdier: hver 1 sammenligning og 0 appends. Samlet:

$$T(n)=n$$

Alle værdier identiske; $T(n)=n$

Spørgsmål C.2

Hvad skal gælde for listen values for at opnå et worst-case tilfælde, og hvad er worst-case tidskompleksiteten $T(n)$?

Vis svar Skjul svar

Svar C.2

Worst-case opnås når alle værdier er forskellige, så unique_values bliver maksimal.

Antal operationer: $1+2+3+\cdots+n$:

$$T(n)=\frac{n(n+1)}{2}$$

Alle værdier forskellige; $T(n)=n(n+1)/2$

Spørgsmål C.3

Hvad er worst-case kompleksiteten i store-O notation?

Vis svar Skjul svar

Svar C.3

Det største led i worst-case er proportionalt med $n^2$.

$O(n^2)$

def fast_find_unique(values):
    unique_set = set()
    for x in values:
        if not x in unique_set:
            unique_set.add(x)
    return unique_set

For et set er både x not in unique_set og unique_set.add(x) af kompleksitet $O(1)$.

Spørgsmål C.4

Hvad er worst-case kompleksiteten af funktionen fast_find_unique i store-O notation?

Vis svar Skjul svar

Svar C.4

Hver af de $n$ elementer koster $O(1)$ → samlet $O(n)$.

$O(n)$

Se også

Time complexity · Big O · What is an algorithm