Πολυπλοκοτητα

[migf1]

http://forum.ubuntu-gr.org/viewtopic.php?f=61&t=20487&sid=da3469de42a1284916aa504f9e144746&start=10&http

 

Τις έχω κάνει τις ασκήσεις του link ειδικα τις ασκησεις στο TEST YOUR SELF 4 τις ειχα ολες σωστες !!!! Οι αποριες που εχω ουσιαστικα αν τις δεις λυμενες ειναι απλα θελω να δω αμα ειναι σωστα λυμένες.

 

Και ο Tasos9 έχει μπερδευτει? τι διαολο??? απο τοτε εχω να δω την πολυπλοκοτητα απο το 2011!!!! Εκτοτε ουτε που ασχοληθηκα ξανα.

 

Το ότι η πολυπλοκότητα αλλάζει ανάλογα με το τι θα ορίσεις ως μέγεθος του προβλήματος δεν σε κάλυψε; Είπες πως το κατάλαβες αλλά όσα ρωτάς στη συνέχεια γύρω από αυτό συνεχίζουν να περιστρέφονται.

[defacer]

Στο παράδειγμα του defacer (που αναφέρεται σε τετραγωνικό πίνακα) ακόμα και το 18, που δεν είναι πρώτος, δεν μας κάνει γιατί δεν είναι τετράγωνο κάποιου ακεραίου...

 

Ναι. Αλλά το 17 δεν ήταν τυχαίο -- επειδή μπορούσα να επιλέξω πρακτικά οποιοδήποτε αριθμό, επέλεξα τον κοντινότερο πρώτο στο 16 που ήταν το αρχικό παράδειγμα. Η άχρηστη πληροφορία της ημέρας.

[Star_Light]

Το ότι η πολυπλοκότητα αλλάζει ανάλογα με το τι θα ορίσεις ως μέγεθος του προβλήματος δεν σε κάλυψε; Είπες πως το κατάλαβες αλλά όσα ρωτάς στη συνέχεια γύρω από αυτό συνεχίζουν να περιστρέφονται.

 

 

Αφου ξέρεις οτι καμια φορα με πιάνουν τα κολληματα μου και εμενα....

 

υ.γ Θελω οι κοντρες απο εδω μεσα να γινουν και real time σε συζητησεις και απο κοντα... εγω εχω πει παντως οταν το θρεντ της C παει 100 σελιδες οποιος θελει κανουμε meeting... θα χει τρελη πλακα ποιοι ειναι μεσα ?

[migf1]

...

 

1. Μπορει κάποιος να δωσει την βασικη διαφορα μεταξυ επιδοσης και πολυπλοκοτητας??? δεν εβγαλα τα αγγλικα στο complexity ..... Μηπως ειναι αυτο που γραφτηκε οτι η πολυπλοκοτητα δεν μετριέται σε seconds??? ενω η επιδοση μπορει να μετρηθει ας πουμε ? H πολυπλοκοτητα ειναι θεωρητικη ενω ο χρονος εκτελεσης ενος κωδικα πραγματικος. Eνταξει το βρηκα νομιζω

 

http://stackoverflow.com/questions/4915842/difference-between-time-complexity-and-running-time

...

 

Καλημέρα,

 

επίδοση είναι αυτό που στα Αγγλικά λέμε efficiency ή performance, δηλαδή τον πραγματικό χρόνο εκτέλεσης ενός προγράμματος σε συγκεκριμένο hardware. Η πολυπλοκότητα επηρεάζει την επίδοση, αλλά η επίδοση δεν επηρεάζει την πολυπλοκότητα.

 

Όπως καταλαβαίνεις, η επίδοση δεν μπορεί να μεταφραστεί σε ακριβές νούμερο χρόνου για όλα τα hardware, διότι ακριβώς το ίδιο πρόγραμμα μπορεί σε ένα hardware set να εκτελεστεί σε 1/2 δευτερόλεπτο, σε άλλο h/w set να εκτελεστεί σε 1 sec, σε άλλο να εκτελεστεί σε 0.1 sec, και πάει λέγοντας. Ακόμα και στο ίδιο h/w μπορεί ακριβώς το ίδιο πρόγραμμα να εκτελεστεί σε διαφορετικούς χρόνους σε 2 διαφορετικές στιγμές, λόγω εξωγενών του αλγορίθμου παραγόντων, τους οποίους η πολυπλοκότητα συνειδητά αγνοεί/απορρίπτει... ένα τέτοιος χαρακτηριστικός εξωγενής παράγοντας είναι για παράδειγμα ο χρόνος εισαγωγής κι εξαγωγής των δεδομένων, Ι/Ο).

 

Η πολυπλοκότητα από την άλλη μεριά, επιχειρεί να... γενικοποιήσει την συμπεριφορά του αλγόριθμου, με σημείο αναφοράς τα βήματα εκτέλεσης του αλγόριθμου (που εν πολλοίς σημαίνει loop iterations) σε σχέση με τα δεδομένα του προβλήματος. Όχι δηλαδή το πόσο γρήγορα εκτελείται το πρόγραμμα σε απόλυτα νούμερα, αλλά το με τι ρυθμούς κλιμακώνεται ο χρόνος εκτέλεσης όσο μεγαλώνουν τα δεδομένα του προβλήματος τείνοντας προς το άπειρο.

 

Είναι απόλυτα σύνηθες και αναμενόμενο, 2 αλγόριθμοι να έχουν ακριβώς την ίδια big-Oh πολυπλοκότητα αλλά σε πραγματικές συνθήκες ο ένας από τους 2 να είναι πάντα ταχύτερος από τον άλλον.

 

Αυτά στα εξηγεί και το link που σου έδωσα από το University of Wisconsin Madison, και για την συγκεκριμένη απορία που εκφράζεις θα σου πρότεινα να εστιάσεις στην ενότητα: When constants matter και πιο συγκεκριμένα στην 1η της παράγραφο (καθώς και στις 3 πρώτες παραγράφους της ενότητας: Introduction).

 

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

 

Όπως καταλαβαίνουμε όμως όλοι όσοι δεν είμαστε... καλλιτέχνες team leaders αυτό από μόνο του δεν είναι ικανή συνθήκη για συμπεράσματα ως προς τις ακριβείς επιδόσεις του αλγόριθμου σε πραγματικές συνθήκες, ιδίως σε resource critical εφαρμογές ή σε resource critical μέρη των εφαρμογών (τα resources, όπως εξηγεί και το link είναι η CPU, η μνήμη, η χωρητικότητα, το network bandwdth, κλπ... σημείωσε πως η πολυπλοκότητα υπολογίζεται ξεχωριστά για κάθε resource, και συχνά καταλήγουν σε αντιστρόφως ανάλογες επιδόσεις... για παράδειγμα συνήθως ένας αλγόριθμος βελτιστοποιημένος για CPU το κάνει εις βάρος της μνήμης, ή το ανάποδο, κλπ).

 

Τα resources είναι κατά κανόνα έτσι κι αλλιώς περιορισμένα, οπότε εκ των πραγμάτων η αρχή της big-oh notation πολυπλοκότητας (και όχι μόνο αυτής) να περιγράφει ρυθμό κλιμάκωσης όσο τα δεδομένα τείνουν στο άπειρο, "φωνάζει" πως σε πραγματικές συνθήκες πολύ συχνότερα από ότι νομίζουν όσοι ξέρουν να δουλεύουν μονάχα με με "black boxes" χρειάζεται περαιτέρω εξειδίκευση σε ότι αφορά τις πραγματικές επιδόσεις του αλγόριθμού μας.

 

Κι εδώ αρχίζουν τα πραγματικά δύσκολα, τα επονομαζόμενα και niche... τα δηλαδή όχι κατάλληλα για προγραμματιστές της σειράς, ενίοτε ούτε καν για πολύ καλούς προγραμματιστές αλλά σε άλλους τομείς προγραμματισμού.

 

Εκεί λοιπόν χρειάζεται να εξειδικεύσουμε πλέον τον αλγόριθμό μας, είτε...

 

α) για συγκεκριμένο hardware (επίσης κάτι πολύ περισσότερο συνηθισμένο από ότι νομίζουν όσοι ξέρουν να δουλεύουν μονάχα με black-boxes ή θεωρούν την Ελλάδα το ταβάνι των φιλοδοξιών τους) π.χ. κινητά, παιχνιδοκονσόλες, κάρτες γραφικών/ήχων, microcontrolers, κλπ)

 

β) για εγγυημένα καλύτερες επιδόσεις συγκριτικά με την αρχική ένδειξη της big-oh πολυπλοκότητας (ή όποιας άλλης) του επιλεγμένου αλγόριθμου, ανεξάρτητα με το hardware στο οποίο θα τρέξει ο αλγόριθμος, αλλά με κάποια πρόβλεψη για άνω οριοθέτηση των resources, συνήθως με πρόβλεψη για τα επόμενα 2-3 χρόνια (ή περισσότερο ή λιγότερο, ανάλογα την εφαρμογή και το πεδίο δράσης της). Σε αυτή την κατηγορία εμπίπτουν π.χ. systems programming, game engines, cryptography & security, κλπ.

 

Το α) είναι κατά κανόνα πιο εύκολο από το β) γιατί έχουμε πλήρη γνώση κι έλεγχο σε όλο το εύρος του hardware για το οποίο προορίζεται το πρόγραμμά μας, που σημαίνει πως μας δίνει σημαντικά μεγαλύτερη ευχέρεια και δυνατότητα να κοντρολάρουμε προς όφελός μας και τους εξωγενείς παράγοντες, τους οποίους εξορισμού δεν λαμβάνει υπόψη της η big-oh πολυπλοκότητα.

 

Μια ακόμα σημαντική σημείωση είναι πως όταν μιλάμε για οριοθετημένα δεδομένα, το είδος των δεδομένων είναι δυνατόν να καταστήσει έναν αλγόριθμο μεγαλύτερης πολυπλοκότητας ταχύτερο από έναν αντίστοιχο μικρότερης πολυπλοκότητας, για ένα συγκεκριμένο εύρος τιμών. Ένα τέτοιο γενικό παράδειγμα σου δείχνει και το link που σου παράθεσα, στην 3η παράγραφο της ενότητας When constants matter. Συγκεκριμένα δείχνει πως για δεδομένα με τιμές μικρότερες του 10^4 ο O(N^2) αλγόριθμος του παραδείγματος εκείνου τρέχει ταχύτερα από τον αντίστοιχο O(N).

 

Συνδέοντας λοιπόν αυτό το νήμα με εκείνο για το ξεκίνημα στον προγραμματισμό, είναι αποδεδειγμένο πως δεν υπάρχουν πανάκειες, ούτε γλώσσες πασπαρτού, ούτε programming paradigms καλύτερα ή χειρότερα έτσι γενικώς κι αορίστως. Ούτε καν στην πολυπλοκότητα.

 

 

Επεξ/σία 25 Μαρτίου 2013 από migf1

[Star_Light]

Eυχαριστω migf1. Σωστα κατάλαβα την διαφορα μεταξυ επιδοσης και πολυπλοκοτητας λοιπον. Αυτο που λες το εχω υποψιν μου για την τετραγωνικη οταν έχουμε να επιλυσουμε μονο μικρά προβληματα το λεει ξεκαθαρα και στην παρουσια του αλγοριθμου της φυσαλιδας στην Wikipedia αν θυμαμαι καλα.

 

[migf1]

Όντως το έχεις πιάσει σωστά, μιας και το είχες γράψει κιόλας επιγραμματικά στην τελευταία φράση της παράθεσης που έκανα.

 

Απλά θεώρησα χρήσιμο να το αναλύσω περαιτέρω μιας και τυγχάνει να το γνωρίζω το συγκεκριμένο αντικείμενο, με την ελπίδα πως θα βοηθήσει κι άλλα παιδιά που διαβάζουν το φόρουμ.

 

[Star_Light]

Eννοειται πολυ καλα εκανες!!!!!!!

[giorgos147]

Επαναφέρω το θέμα, επειδή όσες δημοσιεύσεις και αν είδα, όσο και αν έψαξα, δεν είμαι σίγουρος για αυτά που κάνω.

 

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

Τώρα, ας θεωρήσουμε ότι έχουμε δύο nested λούπες. Η πρώτη (ας πούμε ότι τρέχει μέχρι q), γνωρίζουμε εξαρχής ότι θα τρέξει 50 φορές, η δεύτερη όμως λούπα, εξαρτάται από την τιμή της p. (Στη δεύτερη λούπα μάλιστα καλείται ρουτίνα κ.ο.κ.)

Όλες οι άλλες ενέργειες πέρα από τις λούπες, εκτελούνται σε constant χρόνο.

Οπότε, η πολυπλοκότητα εδώ είναι; Προσωπικά, θεωρώ ότι είναι Ο(q*p). Βέβαια, θα μπορούσε η q να θεωρηθεί και αυτή "σταθερά", ειδικά για πολύ μεγάλες τιμές p >> q (??), αλλά.

 

Χαζά λέω, ε; 

Σίγουρα κάτι χάνω.

[k33theod]

Δες εδώ ίσως σε φωτήσει

http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

[giorgos147]

Σε ευχαριστώ πολύ.

 

Δυστυχώς πάλι δεν κατάφερα να καταλήξω κάπου.

Ας πούμε στη περίπτωση μου, πρακτικά το q παραμένει σταθερό, ενώ το p είναι αυτό από το οποίο εξαρτάται άμεσα η μεταβολή της πολυπλοκότητας του αλγόριθμου.

Όμως, το "worst case scenario" εδώ είναι και το q και το p να λάβουν τιμές (γιατί πρακτικά και το q, ναι, υπό συνθήκες μπορεί να αλλάξει) που να τείνουν στο άπειρο ξερωγώ. Εκεί δε θα έχουμε O(q*p); Και μόνο αν θεωρήσουμε τις 2 υποπεριπτώσεις: ότι p>>q ή q παραμένει σταθερό για κάθε τιμή του p, τότε δε θα μπορούσαμε να ισχυριστούμε ότι η πολυπλοκότητα είναι O(q);

 

Ελπίζω να γίνομαι κατανοητός.

[defacer]

Κατ' αρχήν πρέπει να ξεκινήσεις με πιο συστηματική ανάλυση του τι κάνουν οι τιμές σου, αυτά τα p και q που δεν καταλαβαίνω καθόλου απ' αυτά που λες πώς μπορεί να σχετίζονται. Πότε "παραμένει το q σταθερό"; Και όταν δεν παραμένει τι ακριβώς κάνει; Πώς εξαρτάται το τι θα κάνει το εσωτερικό λουπ από το p με μαθηματικούς όρους;

[giorgos147]

Ναι, η περιγραφή μου είναι κάκιστη. Απλά πρόκειται για εργασία και ήθελα να είμαι όσο το δυνατόν "εκτός".

 

Πρακτικά, αυτό που ήθελα να πω με το "το q παραμένει, σχεδόν πάντα, σταθερό ενώ το p όχι", είναι ότι: Για τη συγκεκριμένη υλοποίηση, και για το σύνολο των εκτελέσεων που θα την επαναλάβουμε για να λάβουμε τους χρόνους εκτέλεσης της, αλλάζουμε μόνο την τιμή του p και του q παραμένει πάντοτε σταθερή. Οπότε, για το συγκεκριμένο τρόπο εκτέλεσης της υλοποίησης, ενώ αλλάζουμε το p, το q παραμένει σταθερό. Οπότε δε γνώριζα αν πρέπει να το λάβω υπ'όψιν στην πράξη της πολυπλοκότητας. Απλά είχα στο μυαλό μου ότι "ναι, εντάξει, αλλά αν έρθει ο defacer και τρέξει την υλοποίηση, μπορεί εκτός του p να πειράξει και το q, έτσι, επειδή ήθελε". Δεν ξέρω αν έγινα πιο κατανοητός.

 

Τέλος πάντων. Εν τέλει, και επειδή δε θέλω να γράφω χαζά, ρώτησα τον καθηγητή μου, προκειμένου να είμαι σίγουρος για το αν ο συλλογισμός μου είναι σωστός, και μου απάντησε ότι είναι σωστή σκέψη.

 

Σας ευχαριστώ και τους δύο για το χρόνο σας^. 

[NickSym]

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

Γενικοτερα και πιο συγκεκριμενα ισχυει το παρακατω.

 

Η πολυπλοκοτητα του

void main(void) {

int i;

int j;

 

for(i = 0; i < 5;i++) {

for(j = 0; j < 5;j++) {

}

}

}

 

Ειναι Ο(5 * 5) = Ο(1) Για σταθερες τιμες θεωρουμε οτι ειναι αμελητεες κι αρα Ο(1)

 

void func(int x, int y) {

int i;

int j;

 

for(i = 0; i < x;i++) {

for(j = 0; j < y;j++) {

}

}

}

 

Εδω ειναι Ο(x*y) ή Ο(x^2) αν x = y

 

void func1(int x) {

int i;

 

for(i = 0; i < x;i++) {

}

}

 

Εδω ειναι Ο(x).

 

void func2(int x) {

int i;

int j;

 

for(i = 0; i < x;i++) {

for(j = 0; j < 5;j++) {

}

}

}

 

Εδω Ο(5*x) = O(x). Γιατι 5 σταθερα τιμη.

[giorgos147]

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

Γενικοτερα και πιο συγκεκριμενα ισχυει το παρακατω.

 

Σε ευχαριστώ πολύ Nick.

 

Νομίζω το έπιασα. Κάτι τελευταίο για να το σιγουρέψω.

 

Όταν έχουμε μία σειρά από κλήσεις ρουτινών, πρακτικά για να μετρήσουμε τη "συνολική πολυπλοκότητα", δεν "επιστρέφουμε" στην αρχική ρουτίνα που κάλεσε όλες τις άλλες ρουτίνες τη πολυπλοκότητα αυτών που κάλεσε; Δεν ξέρω αν είναι, πάλι, σωστό έτσι όπως το διατυπώνω.

 

Π.χ. Ρουτίνα 1 --> Ρουτίνα 2 --> Υπορουτίνες 3 και 4 που επιστρέφουν κάτι στην 2

Άρα, η συνολική πολυπλοκότητα της ρουτίνας 1, και άρα της υλοποίησης, είναι: Πολυπλοκότητα Ρουτίνας 1 * Πολυπλ. Ρουτίνας 2 που η πολυπλοκότητα της 2 θα είναι η πολυπλοκότητα της (π.χ. αν έχει loop/while κ.λπ. χωρίς σταθερές τιμές) επί τις πολυπλοκότητες που επιστρέφουν οι υπορουτίνες: πολυπλ. υπορουτίνας 3 * πολυπλ. υπορ. 4

 

Σωστά;

 

Η βασικά για να είμαι πιο σαφής, αν στη δεύτερη nested λούπα καλείται μία ρουτίνα, τότε θα είναι (P*Q*πολυπλοκότητα της καλούμενης ρουτίνας)

[NickSym]

Σε ευχαριστώ πολύ Nick.

 

Νομίζω το έπιασα. Κάτι τελευταίο για να το σιγουρέψω.

 

Όταν έχουμε μία σειρά από κλήσεις ρουτινών, πρακτικά για να μετρήσουμε τη "συνολική πολυπλοκότητα", δεν "επιστρέφουμε" στην αρχική ρουτίνα που κάλεσε όλες τις άλλες ρουτίνες τη πολυπλοκότητα αυτών που κάλεσε; Δεν ξέρω αν είναι, πάλι, σωστό έτσι όπως το διατυπώνω.

 

Π.χ. Ρουτίνα 1 --> Ρουτίνα 2 --> Υπορουτίνες 3 και 4 που επιστρέφουν κάτι στην 2

Άρα, η συνολική πολυπλοκότητα της ρουτίνας 1, και άρα της υλοποίησης, είναι: Πολυπλοκότητα Ρουτίνας 1 * Πολυπλ. Ρουτίνας 2 που η πολυπλοκότητα της 2 θα είναι η πολυπλοκότητα της (π.χ. αν έχει loop/while κ.λπ. χωρίς σταθερές τιμές) επί τις πολυπλοκότητες που επιστρέφουν οι υπορουτίνες: πολυπλ. υπορουτίνας 3 * πολυπλ. υπορ. 4

 

Σωστά;

 

Η βασικά για να είμαι πιο σαφής, αν στη δεύτερη nested λούπα καλείται μία ρουτίνα, τότε θα είναι (P*Q*πολυπλοκότητα της καλούμενης ρουτίνας)

 

Ναι, σωστά. Έχεις πιάσει το νόημα.

Αλλά η καλούμενη συνάρτηση θα πρέπει να κληθεί μέσα σε έναν βρόγχο, αν κληθεί μόνο μια φορά τότε προσθέτεις την πολυπλοκότητα της με αυτή της καλούσας συνάρτησης, δεν την πολλαπλασιάζεις.

Ουσιαστικά είναι ένα κομμάτι της πολυπλοκότητας της καλούσας συνάρτησης.

 

Ένα καλό παράδειγμα ίσως είναι ο υπολογισμός του παραγοντικού.

Η πολυπλοκότητα του είναι γραμμική, δηλαδή O(n).

 

Αν το κάνεις με loop τότε εύκολα σου βγαίνει O(n), λόγω του πλήθους των επαναλήψεων.

 

Αν το κάνεις αναδρομικά θα σου βγει O(n) γτ θα κληθεί n φορές η ίδια συνάρτηση.

Άρα Αν πολυπλοκότητα:= π τότε π + π + .... + π, με #π = n * π

Η πολυπλοκότητα θεωρείται σταθερή αφού την έχεις υπολογίσει για ένα βήμα, άρα O(n*π) = O(n).