EIΣΑΓΩΓΗ ΣΤΗΝ ΠΟΛΥΠΛΟΚΟΤΗΤΑ

[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
Αυτά Φιλικά

[Star_Light]

Αν έχει λίγο μεγαλύτερο η μικρότερο ρυθμό δεν αλλάζει πολυπλοκότητα(τάξη)
πχ
Ο Α έχει 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 Μονο αλγεβρικά μπορει να προσδιορίσει καποιος την πολυπλοκοτητα ενος αλγοριθμου ε?

[sokoban4ever]

Α μάλιστα. Οποτε μετα απο αυτους τους υπολογισμούς και αυτο που θα βγει θα ειναι συναρτηση του 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

Ελπιζω αυτή την φορά να είμουν πιο ξεκάθαρος...

[Star_Light]

Ελα @sokoban4ever φιλε μου με το φοβερο αβατάρ!!!

Λεω και εγω γιατι σκάλωσα.... Και εγω εκανα trace τον bubble sort
απλα σου λεω κατι λιγο που μου διαφευγει ακομη ειναι οκ... εκανα trace τον αλγοριθμο
με χαρτι και μολυβι και πως τωρα εγω θα καταλαβω οτι ειναι εκθετικός ή τετραγωνικός.
Αν ρωταω πραγματα που θα μπορουσα να βρω με μια απλη αναζητηση οκ μην μου απαντήσετε
επειδη βλεπω πως καθε φορα μου παραθετεις αρθρα αλλα δεν εχω πολυ χρονο να τα κοιταξω καλα
γιατι ειναι και στα Αγγλικα και εχω ενα μικρο θεματακι με τα Αγγλικα.... να φανταστεις δεκεβρη δινω Λοουερ χαχαχα
με τα 16χρονα μαζι φιλε!!!! Θα γελάει ο κοσμος!

παντως
Ευχαριστω πολυ. Απλα ηθελα να μαθω λιγο τι σημαινει πολυπλοκοτητα.

P.S Βεβαια αυτο ισως βγαινει και με τα tips που μου ειπε και ο Τασος... Ν*Ν και ετσι.

[sokoban4ever]

Ελα @sokoban4ever φιλε μου με το φοβερο αβατάρ!!!

Λεω και εγω γιατι σκάλωσα.... Και εγω εκανα trace τον bubble sort
απλα σου λεω κατι λιγο που μου διαφευγει ακομη ειναι οκ... εκανα trace τον αλγοριθμο
με χαρτι και μολυβι και πως τωρα εγω θα καταλαβω οτι ειναι εκθετικός ή τετραγωνικός.
Αν ρωταω πραγματα που θα μπορουσα να βρω με μια απλη αναζητηση οκ μην μου απαντήσετε
επειδη βλεπω πως καθε φορα μου παραθετεις αρθρα αλλα δεν εχω πολυ χρονο να τα κοιταξω καλα
γιατι ειναι και στα Αγγλικα και εχω ενα μικρο θεματακι με τα Αγγλικα.... να φανταστεις δεκεβρη δινω Λοουερ χαχαχα
με τα 16χρονα μαζι φιλε!!!! Θα γελάει ο κοσμος!

παντως
Ευχαριστω πολυ. Απλα ηθελα να μαθω λιγο τι σημαινει πολυπλοκοτητα.

P.S Βεβαια αυτο ισως βγαινει και με τα tips που μου ειπε και ο Τασος... Ν*Ν και ετσι.

Για σου φίλε μου Star_Light με το φοβερο γούστο
Λοιπόν το big O notation όπου το O βγαίνει από το "order of" (τάξης του) στα ελληνικά...
είναι το άνω κατώφλι της καμπύλης και δείχνει το πόσο μπορεί να φτάσει ο αλγόριθμος.
Αν έχουμε ένα αλγόριθμο και κάνει μόνο

Κώδικας: Επιλογή όλων

int greeting = "Hello";
printf("%d World\n",&greeting);

Αυτός έχει πολυπλοκότητα Ο(1) όπου στο άξονα
θα σχημάτιζε μια παράλληλη ευθεία διότι δεν έχει ρυθμό ανάπτυξης (έχει 0)
, πάντα θα κάνει ένα συγκεκριμένο χρόνο να ολοκληρωθεί (το συγκεκριμένο παράδειγμα θεωρητικά μόνο γιατι εξαρτάται από το μηχάνημα , το λειτουργικό και το φόρτο εργασίας του υπολογιστή...)
Ορίστε μια εικόνα με μερικές κλασικές καμπύλες που φένονται ποιές είναι με το μάτι (πέρα από την μέθοδο με την παράγωγο...)

[Star_Light]

hehehehe τα σπαει ο ελεφαντας ,τι τον πότισες και μουρλάθηκε

Δηλαδη αρκει να δινεις καποια εισοδο να δεις τι εξοδο παιρνεις και μετα
να φτιαχνεις τα σημεια σε ενα καρτεσιανο συστημα και να βλεπεις την συμπεριφορα της καμπυλης της γραφικης
παραστασης που σχηματιζεται για να αποφανθεις και για την πολυπλοκοτητα ε?

[Tasos09]

Λεπόν σταρλαιτ. Έγραψα για 1 φεγγάρι και εξαφανίστηκα. Για την πολυπλοκότητα βρίσκεις το πλέον χρονοβόρο σημείο και προσπαθείς να υπολογίσεις τις πράξεις που θα γίνουν συναρτήσει της εισόδου.
Έτσι στη bubblesort είναι προφανές ότι όλες οι πράξεις γίνονται μέσα στο for. Συνολικά βλέπεις ότι γίνονται (Ν-1)+(Ν-2)+...+2+1 πράξεις. Απ το γνωστό τύπο των αριθμητικών προόδων προκύπτει ότι αυτό κάνει N(Ν-1)/2. Αν κάνεις τις πράξεις θα βγει ½(Ν²-Ν). Το ½ είναι σταθερά, οπότε ασυμπτωτικά δε μας αφορά. Το Ν είναι αμελητέο μπροστά στο Ν² για μεγάλες τιμές και έτσι συνολικά η πολυπλοκότητα είναι Ο(Ν²).

[Star_Light]

Λεπόν σταρλαιτ. Έγραψα για 1 φεγγάρι και εξαφανίστηκα. Για την πολυπλοκότητα βρίσκεις το πλέον χρονοβόρο σημείο και προσπαθείς να υπολογίσεις τις πράξεις που θα γίνουν συναρτήσει της εισόδου.
Έτσι στη bubblesort είναι προφανές ότι όλες οι πράξεις γίνονται μέσα στο for. Συνολικά βλέπεις ότι γίνονται (Ν-1)+(Ν-2)+...+2+1 πράξεις. Απ το γνωστό τύπο των αριθμητικών προόδων προκύπτει ότι αυτό κάνει N(Ν-1)/2. Αν κάνεις τις πράξεις θα βγει ½(Ν²-Ν). Το ½ είναι σταθερά, οπότε ασυμπτωτικά δε μας αφορά. Το Ν είναι αμελητέο μπροστά στο Ν² για μεγάλες τιμές και έτσι συνολικά η πολυπλοκότητα είναι Ο(Ν²).

Ευχαριστω τάσο!!! Και εγώ χάνομαι γιατι έχω μπλεξει με τα δικα μου. Αλλα οκ