Πολυπλοκότητα αλγορίθμων — μέτρηση συγκρίσεων πριν από τον χρόνο

Σύμβαση και μέγεθος εισόδου

Μία τοπική μηχανή αναζήτησης ελέγχει ποια ζητούμενα ονόματα υπάρχουν στον κατάλογο. Όρισε n ως το πλήθος ζητήσεων και m ως το πλήθος διαθέσιμων ονομάτων. Η ένθετη αναζήτηση μπορεί να κάνει n*m συγκρίσεις όταν όλα τα ονόματα λείπουν. Μία άλλη λύση δημιουργεί σύνολο κατακερματισμού, συνήθως σε O(m) χρόνο με O(m) επιπλέον μνήμη, και μετά εκτελεί αναμενόμενες αναζητήσεις O(1). Για μικρά δεδομένα το κόστος κατασκευής του συνόλου μπορεί να είναι μεγαλύτερο από το όφελος.

Εκτελέσιμο παράδειγμα Python 3

Αποθήκευσε ως complexity_lab.py και εκτέλεσε python3 complexity_lab.py. Η πρώτη συνάρτηση μετρά τις πραγματικές συγκρίσεις, ενώ και οι δύο διατηρούν διπλές ζητήσεις στο αποτέλεσμα.

def nested_lookup(left, right):
    found, comparisons = [], 0
    for item in left:
        for candidate in right:
            comparisons += 1
            if item == candidate:
                found.append(item)
                break
    return found, comparisons

def indexed_lookup(left, right):
    index = set(right)
    return [item for item in left if item in index]

left = ['a', 'b', 'z', 'a']
right = ['b', 'a']
found, steps = nested_lookup(left, right)
assert found == ['a', 'b', 'a'] and steps == 7
assert indexed_lookup(left, right) == found
assert nested_lookup([], right) == ([], 0)
try:
    indexed_lookup([[1]], [[1]])
except TypeError:
    pass
else:
    raise AssertionError('unhashable values were accepted')
print('PASS complexity: equivalent membership, measured comparisons')

Τι αποδεικνύεται

Στο δείγμα η ένθετη αναζήτηση κάνει επτά συγκρίσεις, επειδή και το z ελέγχεται χωρίς να βρεθεί. Οι επτά πράξεις δεν διαρκούν πάντα τον ίδιο χρόνο σε όλες τις συσκευές. Τα σύνολα απαιτούν κατακερματίσιμες τιμές με συμβατή ισότητα και συνάρτηση hash· λίστες μέσα σε λίστες προκαλούν TypeError. Μία κακή συνάρτηση κατακερματισμού μπορεί να χειροτερέψει τη συμπεριφορά. Το αναμενόμενο O(1) δεν είναι απόλυτη εγγύηση χειρότερης περίπτωσης.

Ασκήσεις και έλεγχοι

1. Δημιούργησε 100, 1000 και 5000 ζητήσεις χωρίς επιτυχία. Κράτησε το m σταθερό και έπειτα θέσε m=n. Μέτρησε συγκρίσεις.
2. Τοποθέτησε το συχνότερο όνομα στην αρχή και στο τέλος της δεύτερης λίστας. Εξήγησε πώς αλλάζει ο αριθμός βημάτων.
3. Σύγκρινε με τομή δύο συνόλων και εξήγησε γιατί η αφαίρεση των διπλών ζητήσεων αλλάζει το αποτέλεσμα.
4. Μέτρησε χρόνο με time.perf_counter σε επαναλαμβανόμενες εκτελέσεις μετά από προθέρμανση. Κατάγραψε έκδοση Python και συσκευή, μαζί με το επιπλέον κόστος μνήμης.

Παραδοτέα: PASS, πίνακας n/m/συγκρίσεων και απόδειξη αποτυχίας για μη κατακερματίσιμα στοιχεία.