Praktické cvičenie: Asymptotická zložitosť v testoch

Cieľ

Implementujte niekoľko vyhľadávacích funkcií tak, aby boli nielen správne, ale aby mali aj požadovanú asymptotickú zložitosť.

Študent si precvičí:

• lineárne vyhľadávanie O(n),
• binárne vyhľadávanie O(log n),
• detekciu duplicít v lineárnom čase O(n),
• hľadanie dvojice so zadaným súčtom v lineárnom čase O(n),
• rozdiel medzi testom správnosti a testom efektívnosti.

Zadanie

Vytvorte súbor solution.py a implementujte funkcie:

def linear_search(data, target):
    pass

def binary_search(data, target):
    pass

def has_duplicates(data):
    pass

def find_pair_sum(data, target):
    pass

1. linear_search(data, target)

Funkcia dostane zoznam alebo inú postupnosť hodnôt a hľadanú hodnotu.

Vráti:

• index prvého výskytu hodnoty target,
• alebo -1, ak sa hodnota v postupnosti nenachádza.

Požadovaná zložitosť:

• časová zložitosť O(n),
• pamäťová zložitosť O(1).

Príklady:

linear_search([4, 8, 15, 16, 23, 42], 15)
# 2

linear_search([4, 8, 15], 99)
# -1

2. binary_search(data, target)

Funkcia dostane vzostupne zoradenú indexovateľnú postupnosť hodnôt a hľadanú hodnotu.

Vráti:

• index nájdenej hodnoty target,
• alebo -1, ak sa hodnota v postupnosti nenachádza.

Ak sa hodnota v postupnosti nachádza viackrát, môže vrátiť ľubovoľný jej index.

Požadovaná zložitosť:

• časová zložitosť O(log n),
• pamäťová zložitosť O(1).

Nepoužívajte:

• operátor in,
• metódu .index(),
• funkcie bisect_left() alebo bisect_right() z modulu bisect,
• prevod vstupu na list, ak už vstup listom nie je.

Príklady:

binary_search([2, 4, 6, 8, 10], 8)
# 3

binary_search([2, 4, 6, 8, 10], 7)
# -1

3. has_duplicates(data)

Funkcia dostane postupnosť hašovateľných hodnôt.

Vráti:

• True, ak sa niektorá hodnota nachádza vo vstupe aspoň dvakrát,
• False, ak sú všetky hodnoty unikátne.

Požadovaná zložitosť:

• priemerná časová zložitosť O(n),
• pamäťová zložitosť O(n).

Príklady:

has_duplicates([1, 2, 3, 2])
# True

has_duplicates([1, 2, 3, 4])
# False

4. find_pair_sum(data, target)

Funkcia dostane postupnosť celých čísel a cieľový súčet.

Vráti:

• dvojicu hodnôt (a, b), pre ktorú platí a + b == target,
• alebo None, ak taká dvojica neexistuje.

Rovnaký prvok vstupu nesmiete použiť dvakrát. Ak má byť použitá rovnaká hodnota dvakrát, musí sa vo vstupe nachádzať aspoň dvakrát.

Požadovaná zložitosť:

• priemerná časová zložitosť O(n),
• pamäťová zložitosť O(n).

Príklady:

find_pair_sum([2, 7, 11, 15], 9)
# (2, 7)

find_pair_sum([3, 4, 5], 10)
# None

find_pair_sum([5, 1, 5], 10)
# (5, 5)

Poradie hodnôt vo vrátenej dvojici nie je dôležité.

Automatické hodnotenie

Automatické testy majú overovať dve veci:

1. správnosť výsledkov,
2. približnú zložitosť riešenia.

Pri zložitosti je vhodnejšie počítať operácie než merať čas, pretože časové testy môžu byť nestabilné. Testy preto môžu použiť pomocné triedy, ktoré počítajú počet prístupov alebo porovnaní.

Testy správnosti

from solution import (
    linear_search,
    binary_search,
    has_duplicates,
    find_pair_sum,
)

def test_linear_search():
    assert linear_search([4, 8, 15, 16, 23, 42], 15) == 2
    assert linear_search([4, 8, 15, 16, 23, 42], 4) == 0
    assert linear_search([4, 8, 15, 16, 23, 42], 99) == -1

def test_binary_search():
    data = [2, 4, 6, 8, 10, 12, 14]
    assert binary_search(data, 2) == 0
    assert binary_search(data, 8) == 3
    assert binary_search(data, 14) == 6
    assert binary_search(data, 7) == -1

def test_has_duplicates():
    assert has_duplicates([1, 2, 3, 2]) is True
    assert has_duplicates([1, 2, 3, 4]) is False
    assert has_duplicates([]) is False
    assert has_duplicates(["a", "b", "a"]) is True

def test_find_pair_sum():
    pair = find_pair_sum([2, 7, 11, 15], 9)
    assert pair is not None
    assert sum(pair) == 9
    assert set(pair) == {2, 7}

    assert find_pair_sum([3, 4, 5], 10) is None

    pair = find_pair_sum([5, 1, 5], 10)
    assert pair is not None
    assert pair[0] + pair[1] == 10

Test zložitosti pre binary_search

Tento test odhalí riešenie, ktoré namiesto binárneho vyhľadávania prechádza celý vstup.

from solution import binary_search

class CountingSequence:
    def __init__(self, size):
        self.size = size
        self.reads = 0

    def __len__(self):
        return self.size

    def __getitem__(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(index)

        self.reads += 1
        return index * 2

def test_binary_search_uses_logarithmic_number_of_reads():
    data = CountingSequence(1_000_000)

    assert binary_search(data, 1_999_998) == 999_999
    assert data.reads <= 60

Pre milión prvkov je log2(1_000_000) približne 20. Limit 60 ponecháva rezervu na bežné implementácie, ktoré v jednej iterácii prečítajú stredový prvok viac než raz, ale stále odhalí lineárne prechádzanie vstupu.

Test zložitosti pre has_duplicates

Tento test odhalí kvadratické riešenia s vnorenými cyklami.

from solution import has_duplicates

class CountedValue:
    hash_calls = 0
    eq_calls = 0

    def __init__(self, value):
        self.value = value

    def __hash__(self):
        CountedValue.hash_calls += 1
        return hash(self.value)

    def __eq__(self, other):
        CountedValue.eq_calls += 1
        return self.value == other.value

def test_has_duplicates_is_linear_on_unique_values():
    CountedValue.hash_calls = 0
    CountedValue.eq_calls = 0

    data = [CountedValue(i) for i in range(10_000)]

    assert has_duplicates(data) is False
    assert CountedValue.hash_calls <= 30_000
    assert CountedValue.eq_calls <= 10

Riešenie cez set používa približne lineárny počet hašovaní. Kvadratické riešenie cez porovnávanie každého prvku s každým prekročí limit porovnaní.

Test zložitosti pre find_pair_sum

Tento test používa väčší vstup. Kvadratické riešenia budú pri skrytých testoch príliš pomalé alebo prekročia limit operácií.

from solution import find_pair_sum

def test_find_pair_sum_large_input():
    data = list(range(100_000))

    pair = find_pair_sum(data, 199_997)

    assert pair is not None
    assert pair[0] + pair[1] == 199_997

Odporúčaná stratégia riešenia

• linear_search: jeden cyklus cez vstup.
• binary_search: interval left, right, stred mid, zmenšovanie intervalu na polovicu.
• has_duplicates: množina už videných hodnôt.
• find_pair_sum: množina už videných hodnôt a hľadanie doplnku target - value.

Hodnotenie

Časť	Body
linear_search	2
binary_search - správnosť	3
binary_search - logaritmický počet prístupov	3
has_duplicates - správnosť	2
has_duplicates - lineárne riešenie	3
find_pair_sum - správnosť	3
find_pair_sum - lineárne riešenie	2
Čitateľnosť kódu a názvy premenných	2

Spolu: 20 bodov.

Bonus

Pridajte funkciu:

def complexity_report():
    pass

Funkcia vráti slovník s očakávanými zložitosťami:

{
    "linear_search": "O(n)",
    "binary_search": "O(log n)",
    "has_duplicates": "O(n)",
    "find_pair_sum": "O(n)",
}

Táto časť je jednoduchá na automatické overenie a núti študenta pomenovať zložitosť implementovaných algoritmov.

Previous Post Next Post