Αλγόριθμοι και πολυπλοκότητα — DedSec Project

Εκτίμησε πόσο αυξάνεται η εργασία με την είσοδο. Μία διέλευση n στοιχείων είναι O(n), δύο ένθετες πλήρεις διελεύσεις συνήθως O(n²). Προτίμησε ορθό και ευανάγνωστο κώδικα.

Λυμένο παράδειγμα

def find_item(items, wanted):
    for item in items:
        if item == wanted:
            return True
    return False

print(find_item([2, 4, 8], 4))

Άσκηση

Πόσες συγκρίσεις χρειάζονται στη χειρότερη περίπτωση για 100 στοιχεία;

Λύση / υπόδειξη

Έως 100 συγκρίσεις (γραμμικός χρόνος).

Η πολυπλοκότητα είναι μοντέλο, όχι χρονόμετρο

Το Big-O περιγράφει αύξηση κόστους. Διπλός βρόχος μπορεί να είναι O(n²), αναζήτηση σε hash set O(1) κατά μέσο όρο, sort συνήθως O(n log n). Όρισε τι μετράς ως n και ποια πράξη κοστίζει. Η μνήμη διαφέρει σε streaming και materialization.

def duplicates(values):
    seen=set()
    for value in values:
        if value in seen:return True
        seen.add(value)
    return False
assert duplicates([2,4,2])
assert not duplicates([2,4,6])

Έχει μέσο χρόνο O(n) και πρόσθετη μνήμη O(n). Σύγκρινέ το με nested loops O(n²) σε χρόνο, O(1) επιπλέον μνήμη.

Άσκηση: λίστες 100, 1.000, 10.000 στοιχείων· επαναλαμβανόμενες μετρήσεις, median, εξήγηση γιατί μόνο το timing δεν αποδεικνύει asymptotic bound.

Δυαδική αναζήτηση και αμετάβλητο διάστημα

def lower_bound(items, target):
    lo, hi = 0, len(items)
    while lo < hi:
        mid = (lo + hi) // 2
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
assert lower_bound([], 4) == 0
assert lower_bound([1, 3, 3, 8], 3) == 1
assert lower_bound([1, 3, 3, 8], 4) == 3

Η είσοδος πρέπει να είναι ταξινομημένη. Σε κάθε επανάληψη διατηρείται το διάστημα πιθανών απαντήσεων και μικραίνει· με διπλές τιμές πρέπει να βρεθεί η πρώτη κατάλληλη θέση. Το αποτέλεσμα είναι θέση εισαγωγής και δεν αποδεικνύει ότι ο στόχος υπάρχει. Σύγκρινε με γραμμική αναζήτηση σε τυχαίες ταξινομημένες λίστες με σταθερό seed, κενή είσοδο και στόχους εκτός ορίων. Αν ταξινομείς την είσοδο ξανά για κάθε ερώτημα, το συνολικό κόστος περιλαμβάνει O(n log n) και όχι μόνο O(log n). Πηγή: https://docs.python.org/3/library/bisect.html