Αλγόριθμοι ταξινόμησης-merge sort

[lara1985]

Υπάρχει κάποιος που να γνωρίζει πως λύνεται το παρακάτω???????????
(a) Ο αλγόριθμος ταξινόμησης 3-merge sort πάνω σε ένα πίνακα με n στοιχεία δουλεύει ως εξής:
1. διαίρεσε τον πίνακα σε 3 υποπίνακες μεγέθους n/3
2. αναδρομικά ταξινόμησε τους 3 υποπίνακες
3. συγχώνευσε τους 3 υποπίνακες
Εκφράστε την αναδρομική συνάρτηση που περιγράφει την πολυπλοκότητα χρόνου του αλγορίθμου 3-merge sort και υπολογίστε την πολυπλοκότητα χρόνου του, εάν το n είναι δύναμη του 3.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Υπάρχει κάποιος που να γνωρίζει πως λύνεται το παρακάτω???????????
(a) Ο αλγόριθμος ταξινόμησης 3-mergesortπάνω σε ένα πίνακα με nστοιχεία δουλεύει ως εξής:
1. διαίρεσε τον πίνακα σε 3 υποπίνακες μεγέθους n/3
2. αναδρομικά ταξινόμησε τους 3 υποπίνακες
3. συγχώνευσε τους 3 υποπίνακες
Εκφράστε την αναδρομική συνάρτηση που περιγράφει την πολυπλοκότητα χρόνου του αλγορίθμου 3-mergesort και υπολογίστε την πολυπλοκότητα χρόνου του, εάν το n είναι δύναμη του 3.

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

Θα ήθελα λοιπόν, κατ' αρχάς, να μας πεις εσύ μέχρι πού έχεις φτάσει. Έχεις δοκιμάσει να την λύσεις; Αν ναι, ανέβασε κάποιο πρόχειρο και το συζητάμε.

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[lara1985]

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

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

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

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

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[lara1985]

Λοιπόν επειδή τώρα δεν μπορώ να ανεβάσω το αρχείο
Έχω δώσει 12 τιμές, χωρίζω σε τρεις υποπίνακες και σιγά σιγά κάνω την αναδρομή των τιμών και έπειτα τα συγχωνεύω σε έναν άλλο πίνακα. αν θέλεις βοηθάς αλλιώς ευχαριστώ πολύ ακόμη και για το ενδιαφέρον. Δεν σε κοροιδεύω για το ότι έχω κάνει είναι σχεδιασμένο στο χέρι

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[Γιώργος]

Λοιπόν επειδή τώρα δεν μπορώ να ανεβάσω το αρχείο
Έχω δώσει 12 τιμές, χωρίζω σε τρεις υποπίνακες και σιγά σιγά κάνω την αναδρομή των τιμών και έπειτα τα συγχωνεύω σε έναν άλλο πίνακα. αν θέλεις βοηθάς αλλιώς ευχαριστώ πολύ ακόμη και για το ενδιαφέρον. Δεν σε κοροιδεύω για το ότι έχω κάνει είναι σχεδιασμένο στο χέρι

Ωραία, το πας καλά.

Για τον χρόνο εκτέλεσης, έχεις το εξής:

• Εφόσον σπας διά του 3, χρειάζεσαι χρόνο για να φτάσεις μέχρι το "τέλος".
• Για κάθε πινακάκι θέλεις χρόνο για να τον επεξεργαστείς

Οπότε τι χρόνο μας βγάζει;

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.

 

[lara1985]

ευχαριστώ πολύ να σαι καλά με έχεις διιευκολύνει

Σημείωση: Το μήνυμα αυτό γράφτηκε 15 χρόνια πριν. Ο συντάκτης του πιθανόν να έχει αλλάξει απόψεις έκτοτε.