Nov D: De største tal
Best-/worst-case for get_big, Big O, og en lineær top-five-algoritme.
Funktionen nedenfor tager som input en liste med tal og returnerer en ny liste med alle tal større end 1000:
def get_big(numbers):
big_numbers = []
for num in numbers:
if num > 1000:
big_numbers.append(num)
return big_numbersHver sammenligning (num > 1000) og hver tilføjelse (big_numbers.append(num)) tæller som 1 operation.
Længden af numbers er $n$.
Hvad er henholdsvis best-case og worst-case tidskompleksiteten $T(n)$ af funktionen målt i antal operationer?
Vis svar Skjul svar
Algoritmen gennemløber alle $n$ tal og sammenligner med 1000 ($n$ sammenligninger). Alle tal større end 1000 tilføjes til den nye liste.
- Best-case (alle tal $\leq 1000$): $T(n)=n$.
- Worst-case (alle tal $>1000$): $T(n)=2n$.
Best: $T(n)=n$; worst: $T(n)=2n$
Hvad er kompleksiteten i store-O notation?
Vis svar Skjul svar
Både best- og worst-case er lineære (største term proportional med $n$).
$O(n)$
En simpel måde at finde de fem største tal er at sortere listen:
top_five = sorted(numbers)[-5:]Kompleksiteten af sortering er $O(n\log n)$. Alternativt kan man bruge:
top_five = numbers[0:5]
smallest_in_top_five = min(top_five)
for num in numbers[5:]:
if num > smallest_in_top_five:
top_five.remove(smallest_in_top_five)
top_five.append(num)
smallest_in_top_five = min(top_five)Algoritmen starter med de første fem tal. Herefter gennemløbes resten; hver gang et tal er større end det mindste
i top_five, erstattes det mindste. Til sidst indeholder top_five de fem største tal.
Hvad skal gælde for listen numbers for at opnå henholdsvis et best-case og et worst-case tilfælde?
Vis svar Skjul svar
Best-case: de fem største tal ligger først på listen, så top_five aldrig skal opdateres.
Worst-case: hvert nyt tal er større end det mindste i top_five — fx hvis listen er sorteret i stigende rækkefølge.
Best: fem største først; worst: stigende / altid opdater
Hvad er kompleksiteten af denne algoritme i store-O notation?
Vis svar Skjul svar
Algoritmen gennemløber alle tal og foretager en konstant, $O(1)$, mængde beregninger for hvert element (listen top_five har fast længde 5). Samlet er algoritmen $O(n)$.
$O(n)$