Δημοσιεύτηκε: 17 Οκτ 2011, 15:25
sokoban4ever έγραψε:Αν έχει λίγο μεγαλύτερο η μικρότερο ρυθμό δεν αλλάζει πολυπλοκότητα(τάξη)
πχ
Ο Α έχει n^2 + C όπου το C έιναι σταθερά constant και ο Β έχει n^2
τόσο ο Α όσο και ο Β είναι της ίδιας πολυπλοκότητας ίδιας τάξης καθώς το C (constant) θεωρείτε αμελητέο.
Με άλλα λόγια είναι το n είναι 1 είτε 1000000000000000000000000000 η διαφορά τους θα είναι μόνο C...
Φυσικά και αν τους συγκρίνουμε ο Α πρέπει να είναι και ο γρηγορότερος με διαθορά στήθους... C...
Σημείωση :
Η μέθοδος υπολογισμού της πολυπλοκότητας δεν γίνεται με το να βάλεις τιμές και να δείς αν θυμίζει το output κάποια ακολουθία αριθμών αλλά
κοιτώντας βήμα βήμα τον αλγόριθμο και σημειώνοντας ποσες φορες θα εκτελεστεί η X διαδικασία συνθέτεις ένα πολυόνυωμο όπου με αλγεβρικές πράξεις απαλοίφεις επαναλαμβανώμενους όρους και τέλος απλοποιείς το πολυώνυμο.
Παραθέτω κάποια links ξανά ελπίζω να είναι πιο ξεκάθαρα
http://stackoverflow.com/questions/3255 ... 66#4852666
http://www.brpreiss.com/books/opus7/html/page37.html
Αυτά Φιλικά
Α μάλιστα. Οποτε μετα απο αυτους τους υπολογισμούς και αυτο που θα βγει θα ειναι συναρτηση του n οκ. Κοιταξε θα διαβασω τις πηγες που δινεις αλλα αν υπάρχει και κανα παραδειγματακι να μας κανεις για το πως υπολογιζεται αλγεβρικα ας πουμε θα με ενδιεφερε!
Ευχαριστω
P.S Μονο αλγεβρικά μπορει να προσδιορίσει καποιος την πολυπλοκοτητα ενος αλγοριθμου ε?