Ποια είναι η χρονική πολυπλοκότητα της λειτουργίας της διασταύρωσης στο Python;

Η πολυπλοκότητα του χρόνου της λειτουργίας της διασταύρωσης στο Python εξαρτάται από τη μέθοδο που χρησιμοποιείται και το μέγεθος των συνόλων που εμπλέκονται. Εδώ είναι μια κατανομή:

1. Χρησιμοποιώντας τον χειριστή `&` ή τη μέθοδο `` Termection () ':

* Μέση περίπτωση: O (min (len (set1), len (set2)))

* χειρότερη περίπτωση: O (n*m) όπου n είναι το μήκος ενός σετ και m είναι το μήκος του άλλου, αλλά αυτό είναι πολύ απίθανο.

Επεξήγηση:

* Το `set` της Python 'υλοποιείται χρησιμοποιώντας έναν πίνακα κατακερματισμού. Ο αλγόριθμος ουσιαστικά επαναλαμβάνεται μέσω του μικρότερου σετ και ελέγχει εάν κάθε στοιχείο υπάρχει στο μεγαλύτερο σετ. Ο χειριστής `in` σε ένα σετ (έλεγχος για συμμετοχή) λαμβάνει o (1) κατά μέσο όρο λόγω της αναζήτησης πίνακα hash.

* Επομένως, αν το `set1` είναι μικρότερο, επαναλαμβάνεται μέσω` set1` και εκτελεί μια αναζήτηση πίνακα hash στο `set2` για κάθε στοιχείο, με αποτέλεσμα την πολυπλοκότητα O (len (set1)). Η ίδια λογική ισχύει εάν το `set2` είναι μικρότερο.

* Η χειρότερη περίπτωση του O (N* M) θα συμβεί εάν οι συγκρούσεις κατακερματισμού είναι αχαλίνωτες, υποβαθμίζοντας τις καθορισμένες αναζητήσεις από O (1) έως O (N). Αυτό είναι εξαιρετικά ασυνήθιστο με τους καλούς αλγόριθμους κατακερματισμού της Python.

2. Χρησιμοποιώντας τη μέθοδο `intersection_update ()` `

* Μέση περίπτωση: O (len (set)) όπου το set είναι το σετ που θα ενημερωθεί.

* χειρότερη περίπτωση: Ίδιο με το `etrection ()` - απίθανο o (n*m)

Επεξήγηση:

`intersection_update ()` Τροποποιεί το σύνολο στο οποίο ονομάζεται, αφαιρώντας στοιχεία που δεν υπάρχουν στο άλλο σύνολο. Η πολυπλοκότητα του χρόνου είναι παρόμοια με την «διασταύρωση ()» επειδή χρειάζεται ακόμα να ελέγξει τη συμμετοχή στα άλλα σετ.

Παράδειγμα:

`` `Python

set1 ={1, 2, 3, 4, 5}

set2 ={3, 5, 6, 7, 8}

διασταύρωση χρησιμοποιώντας &χειριστή:

intersection_set =set1 &set2

εκτύπωση (etrection_set) # έξοδος:{3, 5}

Διασύνδεση χρησιμοποιώντας τη μέθοδο TRENSECTION ():

intersection_set =set1.intersection (set2)

εκτύπωση (etrection_set) # έξοδος:{3, 5}

Διασύνδεση χρησιμοποιώντας τη μέθοδο intersection_update () (τροποποιεί το set1):

set1.intersection_update (set2)

εκτύπωση (set1) # έξοδος:{3, 5}

`` `

Πίνακας συνοπτικών:

| Μέθοδος | Μέση πολυπλοκότητα χρόνου περίπτωσης | Χειρότερη περίπτωση της πολυπλοκότητας χρόνου (απίθανη)

| ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

| `&` χειριστής | O (min (len (set1), len (set2))) O (n*m) |

| `TRENSECTION ()` | O (min (len (set1), len (set2))) O (n*m) |

| `intersection_update ()` | O (len (set)) O (n*m) |

Key Takeaway: Η λειτουργία διασταύρωσης σε Python είναι γενικά πολύ αποτελεσματική, χάρη στη χρήση των πινάκων κατακερματισμού. Μπορείτε συνήθως να υποθέσετε ότι είναι O (min (len (set1), len (set2))) για πρακτικούς σκοπούς.