Με την δημιουργία αυτου του θρέντ θα παραθέσω 2-3 βασικα πράγματα (ακριβώς οσα μου επιτρέπει η σύντομη "ερευνα" μου πανω στο συγκεκριμένο θέμα της επιστημης των υπολογιστών το οποιο ειναι τεράστιο και φυσικα δεν μπορει να προσεγγισθεί ολοκληρωτικά απο εναν οδηγο πόσο μαλλον απο μια σύντομη έρευνα για αυτο και όσοι γνωρίζετε κατι παραπάνω απο αυτα που θα παρουσιασθούν εδω , μην ντρέπεστε παιδια!!! Μπειτε να συζητήσουμε και να μοιραστούμε αποψεις και γνώση).
================================================================================================================
Περιεχόμενα
- Τί ειναι η Πολυπλοκότητα
- Τι είναι ενας Αλγόριθμος
- Τι είναι ενας Λογάριθμος
- Βασικές Πολυπλοκότητες
================================================================================================================
Πολυπλοκότητα ειναι ο αριθμός των βημάτων που χρησιμοποιούνται για να λύσει το πρόβλημα ένας αλγόριθμος συναρτήσει της εισόδου του (που έχει σχεδιαστεί για αυτο το πρόβλημα) οταν μιλάμε για χρονική πολυπλοκότητα . Η πολυπλοκότητα διαιρείται σε 2 κύριους αρχικούς τομείς ο ένας προσδιορίζει τον χρόνο που χρειάζεται για να λύσει το πρόβλημα ένας δεδομένος αλγόριθμος οπως προαναφέρεται και αρα μιλάμε για χρονική πολυπλοκότητα ενω ο δε άλλος αναφέρεται στους βασικούς πόρους που χρειάζεται ενας αλγόριθμος (μνήμη) οποτε και μιλάμε για χωρική πολυπλοκότητα και στις 2 περιπτώσεις βεβαια οι υπολογισμοί της πολυπλοκότητας γίνονται συναρτήσει της εισόδου . Η πολυπλοκότητα αναφέρεται είτε σαν υπολογιστική είτε σαν Kolmogorov απο το όνομα του Ρώσου Μαθηματικού Kolmogorov
http://en.wikipedia.org/wiki/Andrey_Kolmogorov
Λίγο πριν ξεκινήσει κάποιος να προγραμματίζει θα ήταν αρκετά χρήσιμο να γνωρίζει και να έχει καταλάβει τι ακριβως είναι ενας αλγόριθμος , τι ειναι ακριβώς αυτο που επιχειρεί να υλοποιήσει μεσω κάποιας γλώσσας προγραμματισμού. Σαν έναν πρώτο απλό αλγόριθμο θα μπορούσαμε να φανταστούμε το Κόσκινο του Ερατοσθένη ο οποίος ορίζει βήματα για την λύση ενος προβλήματος το οποίο έχει να κάνει με την εύρεση των πρώτων αριθμών απο μια δοθείσα λίστα η οποία ξεκινά απο (2 , .... , n) μιας και τα 0 , 1 δεν αποτελούν πρώτους αριθμούς . Ο αλγόριθμος λοιπον ειναι ένα πλήθος απο βήματα που θα ακολουθήσουμε για να λύσουμε ένα δεδομένο πρόβλημα.
Ποια η διαφορά ενος Αλγόριθμου και μιας Υλοποιήσης ?
Ένας Αλγόριθμος ειναι ανεξάρτητος και ξεχωριστός απο την οποιαδήποτε γλώσσα , και μπορεί φυσικά να εκφραστεί και να υλοποιηθεί
με πολλούς διαφορετικούς τρόπους συμπεριλαμβανομενων και του χαρτιου - μολυβιού . Ο αλγόριθμος ειναι ενα "πλάνο" απο το οποίο γράφεις το προγραμμά σου , είπαμε πως ειναι ανεξάρτητος και η ίδια η διαδικασία του ειναι λιγο - πολυ ενα άυλο πράγμα! Ακριβώς και ένας Ψευδοκώδικας ριναι μια περιγραφή ή αναπαράσταση ενος αλγορίθμου που δεν ειναι τυπικά σε θέση να εκτελεστεί απο τις μηχανές στην μορφή στην οποία βρίσκεται.
Μια Υλοποιήση - εκτέλεση (implementation) λοιπον αναφέρεται σε έναν αριθμό απο πιθανές αναπαραστάσεις του αλγοριθμου που μπορεί να εκτελεστεί απο εναν ΗΥ.
Για παράδειγμα η C δεν γνωρίζει τον τρόπο εκτέλεσης του Ψευδοκώδικα ετσι χρειάζεται να γράψεις τον κωδικα σου σε C σύνταξη.
Τι είναι ένας λογάριθμος???
Και εδω αρχίζουν τα ωραία
, άλλωστε πριν κάποιος επιχειρήσει να διαβάσει πολυπολοκότητες της μορφής -> O(nlogn) θα πρέπει να έχει κατανοήσει τι είναι ενας λογάριθμος . Ένας λογάριθμος είναι η δύναμη στην οποία θα πρέπει να υψωθεί ενας δεδομένος αριθμός (η βάση του η οποία θα δίνεται πάντα) ωστε να παράξει τελικα αυτη την ποσότητα. Για παράδειγμα ο λογάριθμος του 16 με βάση το 2 ποιος είναι? -> log2(16) Ψάχνω εκείνον τον αριθμό ο οποίος όταν υψωθεί στην βάση (δηλαδη στο 2 εδώ) θα μου δώσει το 16. Έφοσον ψάχνω κατι για να το βρώ θα πρέπει να δημιουργήσω μια εξίσωση και επειδή ο άγνωστος ειναι δύναμη τοτε η εξισωσή αυτη θα είναι εκθετική απο ανθρώπινη λοιπον έκφραση σε μαθηματική αναπαράσταση το παραπανω ειναι :
- Κώδικας: Επιλογή όλων
2^x = 16
Το 16 μπορεί να γραφτεί σαν 2^4 επομένως
- Κώδικας: Επιλογή όλων
2^x = 2^4
Εφόσον τα 2 μέλη έχουν ίσες βάσεις μπορώ να εξισώσω τους εκθέτες και να βρώ την λύση της εξίσωσης οποτε πράγματι x=4 , αν προσεξει κάποιος την παραπανω εξίσωση άλλωστε το μονο που μένει για να ισχύει η ισότητα ειναι να βάλω το 4 στο αριστερό εκθέτη
- Κώδικας: Επιλογή όλων
2^4 = 2^4 => 16=16 // η επαλήθευση της εξίσωσης
http://el.wikipedia.org/wiki/%CE%9B%CE% ... E%BF%CF%82
Οπου το μάτι μου έπεσε πανω σε αυτο ->
- Κώδικας: Επιλογή όλων
ln(n!)= ln(1) + ln(2) + .... + ln(n)
στον λογάριθμο δηλαδη του n!
n!=1*2*...*n
σύμφωνα με την ιδιότητα των λογαρίθμων
- Κώδικας: Επιλογή όλων
logb(xy) = logb(x)+logb(y) // b ειναι η βάση
τοτε θα έχουμε αρχικά
- Κώδικας: Επιλογή όλων
ln(n!)=ln(1*2*...*n) => ln(n!) =ln(1) + ln(2) + ... + ln(n)
μια μικρή παρένθεση δηλαδη ως εδω για μια ιδιότητα βασική η οποία βοηθάει στους υπολογισμούς και την εργασία με λογάριθμους.
Και πάμε τωρα να δούμε μερικές βασικές πολυπλοκότητες (μαζι με παράθεση απλων κωδίκων σε C )
- Γραμμική Πολυπλοκότητα Τάξης O(n)
- Τετραγωνική Πολυπλοκότητα Τάξης O(n^2)
Για την γραμμικη πολυπλοκότητα έχουμε τον ακόλουθο κώδικα :
Spoiler: show
ΠΡΟΣΟΧΗ:
Εδώ η χρονική πολυπλοκότητα στο γέμισμα ενος μονοδιάστατου πίνακα ακεραίων αριθμών είναι ίση με n (Για i=0,1,2,...,n)
αυτο ειναι ένα παράδειγμα γραμμικής πολυπλοκότητας εφοσον για δεδομένο n (είσοδος) απο τον χρήστη έχουμε δεδομένη έξοδο (όσα και τα στοιχεία που δίνει ο χρήστης ή που θα δώσει) . Άν είχαμε σταθερή πολυπλοκότητα τοτε τα βήματα θα ήταν προκαθορισμένα!
Πχ =>
Spoiler: show
Ακριβώς 3 βήματα δηλαδη.
Ένας ενδεικτικός κωδικας στην συνέχεια για την τετραγωνική πολυπλοκότητα ειναι ο bubble sort :
Spoiler: show
Τέλος πάμε να δούμε και την λογαριθμική πολυπλοκότητα αλλα αυτη την φορά θα αφήσω στην άκρη την χρονική και θα καταπιαστούμε για λιγο με μια χωρική πολυπλοκότητα .
Οποιοσδήποτε φυσικός αριθμός Ν μπορεί να αναπαρασταθεί σε δυαδική μορφή σε όχι παραπάνω απο log2(N) + 1 bit , θυμηθείτε ή ανατρέξτε στην συζήτηση που έγινε πιο πάνω για τους λογάριθμους!
Έστω οτι θέλω να αποθηκεύσω τον αριθμό 4 σε ενα υπολογιστικό σύστημα , ποσα bit θα χρειαστούν για την αποθηκευση του ?
Σύμφωνα με την παραπάνω πρόταση θα χρειαστούν όχι παραπάνω απο log2(N) + 1 bit . Καταρχήν ψάχνω τον λογάριθμο του 4 με βάση το 2 <=> δηλαδη ψάχνω ΠΟΙΑ ειναι η δύναμη εκείνη στην οποία οταν υψωθεί το 2 (δηλαδή η συγκεκριμένη βάση) θα παράξει τον αριθμό 4 οκ?
Θα χρειαστεί να λύσω την εκθετική εξίσωση
- Κώδικας: Επιλογή όλων
2^x=4
επομένως 2 . Θα χρειαστούν όχι παραπάνω απο log2(4) + 1 bit δηλαδη μέχρι 3.Πραγματικά εφοσον η δυαδική αναπαράσταση του 4 σε ένα υπολογιστικό σύστημα ειναι : 100
Έστω τωρα οτι θέλω να αποθηκεύσω τον 8 τότε :
( log2(8) + 1 ) bit = ( 3 + 1 ) bit = 4 bit πράγματι εφοσον η δυαδική αναπαράσταση του 8 ειναι : 1000
To συμπέρασμα που προκύπτει ειναι το ποσό μνήμης που χρειάζεται για την αποθήκευση του φυσικού Ν αυξάνεται λογαριθμικά με αυτον τον Ν.
Η εργασία υπάγεται στην άδεια Creative Commons Αναφορά-Μη εμπορική χρήση-Παρόμοια διανομή 3.0 Ελλάδα
.
