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

lara1985

Νεοφερμένος

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

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

Γιώργος

Τιμώμενο Μέλος

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

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

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

lara1985

Νεοφερμένος

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

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

Γιώργος

Τιμώμενο Μέλος

Ο Γιώργος αυτή τη στιγμή δεν είναι συνδεδεμένος. Μας γράφει απο Ελβετία (Ευρώπη). Έχει γράψει 30,791 μηνύματα.
Έχω φτάσει μέχρι το τρίτο βήμα δημιουργίας του αλγορίθμου. Έχω φτιάξει δηλαδή το δέντρο απλά δυσκολεύομαι αρκετά στον χρόνο εκτέλεσης
Ωραία, δείξε μία μέχρι πού έχεις φτάσει στην δημιουργία του αλγορίθμου. :)
 

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

lara1985

Νεοφερμένος

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

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

Γιώργος

Τιμώμενο Μέλος

Ο Γιώργος αυτή τη στιγμή δεν είναι συνδεδεμένος. Μας γράφει απο Ελβετία (Ευρώπη). Έχει γράψει 30,791 μηνύματα.
Λοιπόν επειδή τώρα δεν μπορώ να ανεβάσω το αρχείο
Έχω δώσει 12 τιμές, χωρίζω σε τρεις υποπίνακες και σιγά σιγά κάνω την αναδρομή των τιμών και έπειτα τα συγχωνεύω σε έναν άλλο πίνακα. αν θέλεις βοηθάς αλλιώς ευχαριστώ πολύ ακόμη και για το ενδιαφέρον. Δεν σε κοροιδεύω για το ότι έχω κάνει είναι σχεδιασμένο στο χέρι
Ωραία, το πας καλά.

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

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

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

lara1985

Νεοφερμένος

Ο lara1985 αυτή τη στιγμή δεν είναι συνδεδεμένος. Έχει γράψει 4 μηνύματα.
ευχαριστώ πολύ να σαι καλά με έχεις διιευκολύνει
 

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

Χρήστες Βρείτε παρόμοια

  • Τα παρακάτω 0 μέλη και 1 επισκέπτες διαβάζουν μαζί με εσάς αυτό το θέμα:
    Tα παρακάτω 0 μέλη διάβασαν αυτό το θέμα:
  • Φορτώνει...
Top