Δημοσιεύτηκε: 17 Οκτ 2011, 22:06
Star_Light έγραψε:
Α μάλιστα. Οποτε μετα απο αυτους τους υπολογισμούς και αυτο που θα βγει θα ειναι συναρτηση του n οκ. Κοιταξε θα διαβασω τις πηγες που δινεις αλλα αν υπάρχει και κανα παραδειγματακι να μας κανεις για το πως υπολογιζεται αλγεβρικα ας πουμε θα με ενδιεφερε!
Ευχαριστω
P.S Μονο αλγεβρικά μπορει να προσδιορίσει καποιος την πολυπλοκοτητα ενος αλγοριθμου ε?
Είναι λάθος ο όρος αλγεβρικά μάλλον από δικό μου λάθος εννοώ ότι κάνουμε απλοποιήσεις όπως στην άλγεβρα αυτό δεν σημαίνει αλγεβρικος προσδιορισμός διότι δεν είναι ξεχωριστά πράγματα τα πολυώνυμα και οι συναρτήσεις και γραφικές παραστάσεις η παράγωγος η γεωμετρία και άλλα...
Στην Θεωρία υπολογιστών σε κάποια μαθήματα για την πολυπλοκότητα αλγορίθμων γινετε εκτενείς αναφορά τις Ασύμπτωτες -- για την σημειογραφία Ασύμπτωτων καμπυλών ( Asymptotic notation ).(εδώ μελετιούνται τα ανω/κάτω κατώφλια των καμπυλών (upper/lower bound) (1)(3)
Βασικά ναι γίνεται και το αντίστροφο... να πέρνεις όλες τις τιμές μια μια και να βλέπεις την ακολουθία.... τις είδους είναι
Ποιό συγκεκριμένα...
Μπορείς όντως να βάζεις τις τιμες μια μια ( κάνεις trace το output του αλγόριθμο σε κάθε n) και να δημιουργείς μια καμπύλη πάνω
στους άξονες X,Y όμως πρέπει μετά από την κλίση και την μορφή της καμπύλης να μαντέψεις * ποιάς μορφής είναι η συνάρτηση
να είναι της μορφής n^2 + ή λογαριθμική εκθετική κλπ ...
* πχ μπορείς να "μαντέψεις" και μάλιστα τον ακριβές τύπο της καμπύλης με την βοήθεια των παραγώγων (2)
Σημείωση :
Αν και δεν χρειάζεται να ξέρεις τον ακριβώς τύπο της καμπύλης αλλά μόνο τον βαθμό της (την τάξη της) καλό είναι να μπορέις να το βρείς και "διαφορετικά"
(1) http://en.wikipedia.org/wiki/Big_O_notation
(2) http://el.wikipedia.org/wiki/%CE%A0%CE% ... E%BF%CF%82
(3) http://www.brpreiss.com/books/opus4/html/page56.html
Ελπιζω αυτή την φορά να είμουν πιο ξεκάθαρος...
