Dec B: Afstand mellem to sæt af tal

Kvadratisk nærmeste-nabo-afstand mellem to talsæt, tidskompleksitet og Big O.

Et talsæt er en liste af tal, hvor rækkefølgen ikke har betydning. Afstanden mellem to sæt $X$ og $Y$ er summen af den kvadratiske afstand fra hvert tal i $X$ til det nærmeste tal i $Y$:

$$d(X,Y)=\sum_i \min_j\bigl((X_i-Y_j)^2\bigr)$$

def set_distance(X, Y):
    d = 0
    for x in X:
        d += min([(x-y)**2 for y in Y])
    return d

Spørgsmål B.1

Hvis $X=\{5,8,6,9,6\}$ og $Y=\{3,5,5,4,7\}$, hvad er da afstanden $d(X,Y)$?

Vis svar Skjul svar

Svar B.1

$$d(X,Y)=(5-5)^2+(8-7)^2+(6-5)^2+(9-7)^2+(6-5)^2=0+1+1+4+1=7$$

Vi antager at både $X$ og $Y$ indeholder $n$ tal.

Spørgsmål B.2

Hvis vi tæller plus (+=), minus (-) eller opløftet i anden (**2) som én operation hver, hvad er da tidskompleksiteten $T(n)$ af algoritmen?

Vis svar Skjul svar

Svar B.2

For hvert af de $n$ tal i $X$ udføres 1 plus-operation ($n$ i alt). For hvert par $(x,y)$ udføres én minus og én potens → $2n^2$ operationer:

$$T(n)=2n^2+n$$

$T(n)=2n^2+n$

Spørgsmål B.3

Hvad er køretidskompleksiteten af Python-algoritmen i store-O notation?

Vis svar Skjul svar

Svar B.3

Samtlige tal i de to sæt sammenlignes parvis → den dominerende term er $n^2$.

$O(n^2)$

def set_distance_new(X, Y):
    return sum([min([(x-y)**2 for y in Y]) for x in X])

Spørgsmål B.4

Sammenlignet med set_distance, er køretidskompleksiteten af set_distance_new da større, mindre, eller uændret?

Vis svar Skjul svar

Svar B.4

Om funktionen implementeres med en for-løkke eller en list-comprehension har ingen indflydelse på den asymptotiske køretidskompleksitet.

Uændret

Se også

Time complexity · Big O · What is an algorithm