Πώς οι χάρτες κατακερματισμού βελτιστοποιούν τους αλγορίθμους;

Question

IT Interview Practice · Accepted Answer

Ένας **χάρτης κατακερματισμού** (λεξικό) παρέχει **O(1) κατά μέσο όρο** αναζητήσεις, εισαγωγές και διαγραφές. Αντικαθιστώντας τις επαναλαμβανόμενες αναζητήσεις με άμεσες αναζητήσεις, μετατρέπονται πολλοί O(n²) αλγόριθμοι σε O(n) με κόστος O(n) μνήμης.

## Η ιδέα

Αντί να αναζητάς μια λίστα κάθε φορά, αποθήκευσε τις τιμές που έχεις δει σε έναν χάρτη κατακερματισμού και ελέγξε την ιδιότητα μέλους σε σταθερό χρόνο.

## Παράδειγμα: two-sum σε O(n)

```python
def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:               # O(1) lookup
            return (seen[need], i)
        seen[x] = i
    return None

two_sum([2, 7, 11, 15], 9)             # -> (0, 1)
```

Χωρίς τον χάρτη αυτό είναι O(n²); με τον χάρτη, μόνο ένα πέρασμα.

## Κοινές χρήσεις

- **Αφαίρεση διπλοτύπων / ιδιότητα μέλους** με ένα σύνολο.
- **Μέτρηση συχνοτήτων** (`Counter`).
- **Ομαδοποίηση / ευρετηρίαση** κατά κλειδί.
- **Αποθήκευση στη μνήμη / μνημόνευση** αποτελεσμάτων.

## Πολυπλοκότητα

- **Κατά μέσο όρο:** O(1) ανά λειτουργία. **Χειρότερη περίπτωση:** O(n) σε βαριές συγκρούσεις. **Χώρος:** O(n).

## Παγίδες

Τα κλειδιά πρέπει να είναι **κατακερματίσιμα** και αμετάβλητα. Οι συγκρούσεις στη χειρότερη περίπτωση υποβαθμίζουν τη δυνατότητα. Οι χάρτες κατακερματισμού είναι αταξινόμητοι (χρησιμοποιήστε ταξινομημένες παραλλαγές αν η σειρά είναι σημαντική).

## Γιατί είναι σημαντικό

Ο κατακερματισμός είναι η απόλυτα πιο κοινή βελτιστοποίηση σε συνεντεύξεις κωδικοποίησης και πραγματικά συστήματα — μετατρέπει "αναζήτησε ξανά και ξανά" σε "κοίταξε το μία φορά".

Η ανταλλαγή χώρου με χρόνο είναι ένας επανειλημμένος μηχανισμός μηχανικής.

Η μέτρηση συχνοτήτων, η αποθήκευση στη μνήμη και η ευρετηρίαση εξαρτώνται όλες από αυτή τη μία ιδέα.

Η ιδέα

Παράδειγμα: two-sum σε O(n)

Κοινές χρήσεις

Πολυπλοκότητα

Παγίδες

Γιατί είναι σημαντικό

Σχετικές ερωτήσεις