forum.math.uoa.gr

Forum του Τμήματος Μαθηματικών
Ημερομηνία 25 Νοέμ 2017, 07:50

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]




Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 
Συγγραφέας Μήνυμα
 Θέμα δημοσίευσης: Αλγόριθμος
ΔημοσίευσηΔημοσιεύτηκε: 11 Μαρ 2015, 04:36 
Χωρίς σύνδεση
Regular Forumer

Εγγραφη: 02 Σεπ 2012, 18:29
Δημοσ.: 118
Γειά :logo:

Ο αλγόριθμος SELECT βρίσκει το i-οστό μικρότερο από έναν πίνακα εισόδου με n>1 διαφορετικά στοιχεία εκτελώντας τα ακόλουθα βήματα.

1. Χώρισε τα n στοιχεία σε \lfloor \frac{n}{5} \rfloor πεντάδες και ενδεχομένως άλλη μία ομάδα με n \pmod 5 στοιχεία.
2. Βρες τη διάμεσο καθεμιάς από τις \lfloor \frac{n}{5} \rfloor ομάδες, ενώ τα ταξινομώ ταυτόχρονα (κάθε ομάδα).
3. Κάλεσε αναδρομικά τον αλγόριθμο προκειμένου να βρει το διάμεσο στοιχείο των διαμέσων, x.
4. Χρησιμοποιώντας την PARTITION, χώρισε το σύνολο εισόδου ως προς το x.
5. Έστω k η τάξη του στο σύνολο εισόδου. Αν i==k επέστρεψε το x. Αν το i<k, κάλεσε την SELECT(A, p, q-1, i) αλλιώς κάλεσε SELECT(A, q+1, r, i-k)



Πώς μπορούμε να βρούμε το κόστος του βήματος 5 ?


Κορυφή
 Προφίλ  
 
Τελευταίες δημοσιεύσεις:  Ταξινόμηση κατά  
Δημιουργία νέου θέματος Απάντηση στο θέμα  [ 1 δημοσίευση ] 

Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]


Μελη σε συνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες


Δεν μπορείτε να δημοσιεύετε νέα θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να απαντάτε σε θέματα σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να επεξεργάζεστε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση
Δεν μπορείτε να διαγράφετε τις δημοσιεύσεις σας σε αυτή τη Δ. Συζήτηση

Αναζήτηση για:
Μετάβαση σε:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group