Δημοσιεύτηκε: 15 Οκτ 2011, 19:13
Λοιπον τα συμπεράσματα μου εχουν ως εξης :
Δεν αρκεί μονο for ειτε ειναι εμφωλιασμένη ειτε το οτιδηποτε για να αποφανθείς αν η πολυπλοκότητα ειναι τετραγωνική ή οχι
γιατι και να έχεις το προβλημα να επιλυσεις με το γέμισμα ενος πινακα δισδιάστατου αν δώσεις NxN = 10 X 10 εισοδο τοτε και παλι ειναι γραμμικη
η πολυπλοκοτητα μιας και δίνεις 100 στοιχεια για να πάρεις 100 στοιχεία σταθερή επισης δεν ειναι γιατι δεν θα παίρνεις παντοτε 100 στοιχεια.... αναλογα με την εισοδο σου οπως εδειξε και στο παραδειγμα του πιο πανω ο Τασος. Τετραγωνικη πολυπλοκοτητα σημαινει πως βάζω 10 στοιχεια και οι πράξεις βγαινουν 100 ας πουμε... οπως στο παράδειγμα της Wikipedia για τον bubble sort εδω => http://en.wikipedia.org/wiki/Bubble_sort που απο το παράδειγμα του μπορεις να πάρεις 8 στοιχεια σαν εισοδο σε εναν πινακα ας πουμε και τελικα n(n-1) / 2 = 8*7 / 2 = 28 πράξεις ... οσο αυξάνει λοιπον η είσοδος n στον αλγόριθμο τοσο αυξάνει και η έξοδος (τετραγωνικά στον συγκεκριμενο αλγοριθμο) και βάσει αυτης της εξόδου θα μπορέσεις να χαρακτηρίσεις αν ειναι βέλτιστος η χάλια απο θέμα επίδοσης (αν σου λύνει γρηγορα το προβλημα ας πουμε).
Περιμενω και τον Τασο να επιβεβαιωσει αυτα που εγραψα για να τα προσθέσω ωστε ο οδηγος να ειναι ακριβης και σαφής.
P.S Υπάρχουν βεβαια μερικές αποριες ακομη σε στυλ... οταν βάλω σαν 10 στοιχεια εισοδο στον Bubble sort παιρνω 45 πράξεις ενω πιο πανω λεω οτι ξερεις τετραγωνικη σημαινει... βαζω 10 παιρνω 100.... αυτο μου ξεφευγει λιγο οτι... πως μπορω να αποφανθω οτι κατι ειναι τετραγωνικο σε αυτη την περιπτωση και οχι εκθετικο ας πουμε...
ειπες οτι η συναρτηση του παραγοντικου δινει εκθετικη αύξηση
δηλαδη
ενω στον bubble sort
η αύξηση της εξόδου με πιο μικρο ρυθμό ας το πουμε χαρακτηρίζει αν ο αλγοριθμος έχει τετραγωνική ή εκθετική πολυπλοκότητα?????
Δεν αρκεί μονο for ειτε ειναι εμφωλιασμένη ειτε το οτιδηποτε για να αποφανθείς αν η πολυπλοκότητα ειναι τετραγωνική ή οχι
γιατι και να έχεις το προβλημα να επιλυσεις με το γέμισμα ενος πινακα δισδιάστατου αν δώσεις NxN = 10 X 10 εισοδο τοτε και παλι ειναι γραμμικη
η πολυπλοκοτητα μιας και δίνεις 100 στοιχεια για να πάρεις 100 στοιχεία σταθερή επισης δεν ειναι γιατι δεν θα παίρνεις παντοτε 100 στοιχεια.... αναλογα με την εισοδο σου οπως εδειξε και στο παραδειγμα του πιο πανω ο Τασος. Τετραγωνικη πολυπλοκοτητα σημαινει πως βάζω 10 στοιχεια και οι πράξεις βγαινουν 100 ας πουμε... οπως στο παράδειγμα της Wikipedia για τον bubble sort εδω => http://en.wikipedia.org/wiki/Bubble_sort που απο το παράδειγμα του μπορεις να πάρεις 8 στοιχεια σαν εισοδο σε εναν πινακα ας πουμε και τελικα n(n-1) / 2 = 8*7 / 2 = 28 πράξεις ... οσο αυξάνει λοιπον η είσοδος n στον αλγόριθμο τοσο αυξάνει και η έξοδος (τετραγωνικά στον συγκεκριμενο αλγοριθμο) και βάσει αυτης της εξόδου θα μπορέσεις να χαρακτηρίσεις αν ειναι βέλτιστος η χάλια απο θέμα επίδοσης (αν σου λύνει γρηγορα το προβλημα ας πουμε).
Περιμενω και τον Τασο να επιβεβαιωσει αυτα που εγραψα για να τα προσθέσω ωστε ο οδηγος να ειναι ακριβης και σαφής.
P.S Υπάρχουν βεβαια μερικές αποριες ακομη σε στυλ... οταν βάλω σαν 10 στοιχεια εισοδο στον Bubble sort παιρνω 45 πράξεις ενω πιο πανω λεω οτι ξερεις τετραγωνικη σημαινει... βαζω 10 παιρνω 100.... αυτο μου ξεφευγει λιγο οτι... πως μπορω να αποφανθω οτι κατι ειναι τετραγωνικο σε αυτη την περιπτωση και οχι εκθετικο ας πουμε...
ειπες οτι η συναρτηση του παραγοντικου δινει εκθετικη αύξηση
δηλαδη
- Κώδικας: Επιλογή όλων
3!=6
4!=24
5!=120
κτλπ....
ενω στον bubble sort
- Κώδικας: Επιλογή όλων
4 -> 6
5 -> 12
6->15
η αύξηση της εξόδου με πιο μικρο ρυθμό ας το πουμε χαρακτηρίζει αν ο αλγοριθμος έχει τετραγωνική ή εκθετική πολυπλοκότητα?????