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

[thanos713]

Όχι, δεν διαφωνώ, απλά δεν έχει νόημα να πεις ότι εδώ χρησιμοποιείς nested loops, γιατί στην ουσία χρησιμοποιείς ένα loop αφού παίρνεις μία φορά το κάθε δεδομένο. Άμα παίρνεις το ίδιο δεδομένο πάνω από μία φορά, έχει νόημα να πεις nested loops άρα και τετράγωνο.

[Star_Light]

Όχι, δεν διαφωνώ, απλά δεν έχει νόημα να πεις ότι εδώ χρησιμοποιείς nested loops, γιατί στην ουσία χρησιμοποιείς ένα loop αφού παίρνεις μία φορά το κάθε δεδομένο. Άμα παίρνεις το ίδιο δεδομένο πάνω από μία φορά, έχει νόημα να πεις nested loops άρα και τετράγωνο.

 

 

Εγω λεω nested loops στο γεμισμα του πινακα.... εκει χρησιμοποιεις μια περιεργη εκφραση απο οσο ειδα στον κωδικα που εδωσες την οποια δεν τσεκαρισα να σου πω την αληθεια.... επειδη εχω συνηθισει το γεμισμα να γινεται σε C με εμφωλιασμενο loop. Εσυ λες για την υλοποιηση στη C τωρα ή για την διατύπωση του αλγοριθμου????

[thanos713]

Και για τα 2. Ο αλγοριθμός με nested, είναι στην ουσία ο ίδιος και χωρίς nested. Άμα κάτι γίνεται και με nested και χωρίς, είναι γραμμικό, αν όχι, είναι τετράγωνο. 

 

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

[migf1]

 

Ρε παιδια να ρωτησω κατι επειδη βλεπω οτι επικρατει καποιου ειδους συγχυση .... πιστευω οτι μια εμφωλιασμενη επαναληψη δεν εγγυαται παντα οτι θα έχουμε τετραγωνική πολυπλοκοτητα... εχω άδικο?

 

Για παράδειγμα ο κώδικας :

 

 

 
for(i=0; i<4; i++)
for(j=0; j<4; j++)
array[i][j] = some_value;
 

 

Για εισοδο 16 στοιχειων σε έναν πινακα array[4][4] υλοποιει 16 εντολές ανάθεσης κάποιας τιμής .... αρα έχει γραμμικη πολυπλοκοτητα επι των στοιχειων εισοδου.

 

Οταν λεω πολυπλοκοτητα εννοω την χρονικη .... δηλαδη με βαση τα στοιχεια της εισοδου που δεχεται ο αλγοριθμος ποσες πραξεις θα κανει πανω σε αυτα και αρα ποση ωρα θα του παρει να τερματισει τον υπολογισμο που χρειαζεται. Για να γεμισει εναν δισδιάστατο πινακα 4 γραμμών και στηλων θα δεχθει 16 στοιχεια και θα κανει 16 αναθέσεις απο array[0][0] - array[0][3] , array[1][0]-array[1][3] , array[2][0] - array[2][3] ,  array[3][0] - array[3][3]. ( 4 + 4 + 4 + 4) Επομενως σε αυτη την περιπτωση μονο η πολυπλοκοτητα ειναι γραμμική ασχετα αν εχεις ή οχι εμφωλιασμενο loop μεσα.

 

Το n εξαρχης ειναι 16 και μετα 16 θα ειναι δεν καταλαβαινω που η διαφορα.....

 

ετσι οπως το γραφει αυτος εδω δεν σε μπερδευει ?

 

http://datastructuresprogramming.blogspot.gr/2010/02/exercise-for-finding-time-complexity-of.html

 

If we have 2 nested loops,

    for(j=0;j < n;j++)

        for(i=0;i < n;i++)

             {statements;}

then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)

 

 

Καλημέρα,

 

το loop που δίνεις ως παράδειγμα αν το πάρουμε μεμονωμένο έχει εγγυημένα τετραγωνική πολυπλοκότητα Ο(N^2) διότι:

α) το N ισούται με M (ίσο με 4 έκαστο)

β) το statement είναι μια απλή πράξη (basic operation), άρα έχει σταθερή πολυπλοκότητα O(1)

 

Η περίπτωση αυτή είναι ειδική περίπτωση της γενικότερης O(N*M).

 

Όταν ο counter του inner loop εξαρτάται από το N του outer loop (και το statement είναι Ο(1) ) έχεις πάντα O(N^2).

 

Σημείωσε επίσης πως το O notation δεν μετράει χρόνο. Επισημαίνει τη σχέση μεταξύ πράξεων και μεγέθους του προβλήματος.

 

Μια καλή και συνοπτική πηγή: http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

 

Από εκεί και πέρα, επειδή στο συγκεκριμένο παράδειγμα δεν υπάρχει κανένας ουσιαστικός λόγος να διαχωρίσεις το N από το M ως μέγεθος προβλήματος, η πολυπλοκότητα του είναι γραμμική O(Ν), εκφρασμένη με ένα μόνο loop, με τη διαφορά πως εδώ πια μιλάς για διαφορετικό Ν , διαφορετικό μέγεθος δηλαδή (τώρα είναι 16 ενώ πριν ήταν 4).

[thanos713]

Ναι, εκεί ακριβώς πιστεύω είχαμε καταλήξει.

[Star_Light]

Παιδια να ρωτησω κατι για να μην μπερδευομαστε αδικα?

 

Οταν έχεις ένα loop εμφωλιασμενο το οποιο εκτυπωνει ή γεμιζει εναν δισδιάστατο πινακα

 

η πολυπλοκοτητα του ως προς τις πραξεις και συναρτησει της εισοδου ειναι ή δεν ειναι γραμμική?

 

Σε αυτο θελω ενα ξεκαθαρο ναί ή οχι!!!!  Αφου το δοκιμασα χθες και μονος μου και μαλιστα με VLA στην C

 

με μπερδεψε το ποστ του migf1 υπο την εννοια οτι δεν καταλαβαινω το "εκφρασμενη με ενα μονο loop"...

 

Έχεις εισοδο 16 στοιχεια .... εχεις 16 πραξεις. Δεν υπαρχει καμια μεταβολη ως προς την επιδοση... αρα γραμμικη πολυπλοκοτητα. Μηπως εχω καταλαβει κατι λαθος?

 

p.s Btw ωραιο το λινκ που παραθετεις και εχω καποιες αποριες γυμνασιου σε αυτο

 

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

 

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

 

 

2. 

for (i = 0; i < N; i++) {
    for (j = i+1; j < N; j++) {
        sequence of statements
    }
}

 

Ακριβως απο κατω εχει την τιμη i και τον αριθμο των επαναληψεων του εσωτερικου loop προσεξε οτι έχει για Ν-2 η τιμη του i  έχουμε 2 επαναληψεις.... αν N=5 τοτε i = 3 ενω j = 4 και λεει για 2 επαναληψεις οτι θα γινουν λογικα εννοει και την περιπτωση στην οποια ο ελεγχος του βροχου βγαινει ψευδης? μια για 4 < 5 και μια για 5 < 5 . Λογικα αυτο θα ειναι γιατι το μηχανημα κανει μια ακομα πραξη. Οταν έχουμε 2 loops εμφωλιασμενα πολλαπλασιαζουμε ενω στη σειρά προσθέτουμε.

 

3. Οταν λεει οτι το Ν* Ο(1) γινεται Ο(Ν) το Ν μπαινει μεσα αλγεβρικα? ή λες οτι αναμεσα σε Ν και O(1) η χειροτερη περιπτωση που μας ενδιαφερει ειναι το Ο(Ν) αρα ολο αποτιμαται σε Ο(Ν) ?

Επεξ/σία 24 Μαρτίου 2013 από Star_Light

[defacer]

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

 

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

 

Στην πρώτη περίπτωση αν κάνεις κάτι με όλα τα στοιχεία του πίνακα για να λύσεις το πρόβλημα τότε ο αλγόριθμος είναι O(n²). Στη δεύτερη περίπτωση αν κάνεις το ίδιο είναι O(n). Καμία σημασία δεν έχει αν και στις δύο περιπτώσεις κάνεις συνολικά τον ίδιο αριθμό επαναλήψεων; σημασία έχει το με ποιό τρόπο αυξάνεται ο αριθμός των επαναλήψεων όσο αυξάνεται το μέγεθος του προβλήματος.

 

Ένα εύκολο τρικ που μπορείς να χρησιμοποιήσεις σα βοήθημα είναι το εξής: το n πρέπει να μπορεί να πάρει οποιαδήποτε τιμή στο σύνολο των φυσικών αριθμών. Αν με τον ορισμό που έχεις δώσει για το n αυτό δεν έχει νόημα, τότε ο ορισμός σου είναι λάθος και πρέπει να βρεις άλλον. Για παράδειγμα, στην περίπτωση του τετραγωνικού πίνακα δεν είναι ποτέ δυνατόν ο συνολικός αριθμός των επαναλήψεων (που εσύ ορίζεις ως n) να πάρει την τιμή π.χ. 17, προφανώς πάντα θα είναι τέλειο τετράγωνο. Επομένως ο ορισμός σου είναι λάθος. Αντίθετα, αν σα n βαφτίσουμε τη διάσταση του πίνακα τότε μπορεί να πάρει οποιαδήποτε τιμή.

[Star_Light]

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

 

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

 

Στην πρώτη περίπτωση αν κάνεις κάτι με όλα τα στοιχεία του πίνακα για να λύσεις το πρόβλημα τότε ο αλγόριθμος είναι O(n²). Στη δεύτερη περίπτωση αν κάνεις το ίδιο είναι O(n). Καμία σημασία δεν έχει αν και στις δύο περιπτώσεις κάνεις συνολικά τον ίδιο αριθμό επαναλήψεων; σημασία έχει το με ποιό τρόπο αυξάνεται ο αριθμός των επαναλήψεων όσο αυξάνεται το μέγεθος του προβλήματος.

 

Ένα εύκολο τρικ που μπορείς να χρησιμοποιήσεις σα βοήθημα είναι το εξής: το n πρέπει να μπορεί να πάρει οποιαδήποτε τιμή στο σύνολο των φυσικών αριθμών. Αν με τον ορισμό που έχεις δώσει για το n αυτό δεν έχει νόημα, τότε ο ορισμός σου είναι λάθος και πρέπει να βρεις άλλον. Για παράδειγμα, στην περίπτωση του τετραγωνικού πίνακα δεν είναι ποτέ δυνατόν ο συνολικός αριθμός των επαναλήψεων (που εσύ ορίζεις ως n) να πάρει την τιμή π.χ. 17, προφανώς πάντα θα είναι τέλειο τετράγωνο. Επομένως ο ορισμός σου είναι λάθος. Αντίθετα, αν σα n βαφτίσουμε τη διάσταση του πίνακα τότε μπορεί να πάρει οποιαδήποτε τιμή.

 

 

@defacer σχετικα με την πολυπλοκοτητα νομιζω παιζουμε με τις λέξεις τωρα ..... την εχω καταλαβει την έννοια μην πας να πιαστεις να μου την πεις οτι δεν εχω προγραμματιστικη εμπειρια μετα βλεπω τι κανεις με τον migf1 . Απλα εκανα πιο πανω μερικες ερωτησεις ισα ισα για να το σιγουρεψω αυτες μπορεις να τις απαντησεις αν θελεις? αν ναι ευχαριστω αν οχι νο προμπ... Λες οτι σημασια εχει με ποιο τροπο αυξάνεται ο αριθμος των επαναληψεων οσο αυξανεται το μεγεθος του προβληματος... εγω τι ειπα? σου ειπα εχεις 10 στοιχεια σαν εισοδο εχεις 10 επαναληψεις .... αν γινουν 20 παλι τα ιδια θα χεις σαν επαναληψεις ... αρα γραμμικη πολυπλοκοτητα. Για δισδιαστατο πινακα μιλουσαμε οχι για τετραγωνικο ασχετα αμα ειχε ιδιο αριθμο γραμμων και στηλων στην τυχη μπηκε.Aρα μιλαμε για διαστάσεις οχι για διασταση.

 

Οριστε  http://bytes.com/topic/c/answers/394772-filling-2d-array-less-than-o-n-2-time

 

και αλλοι που λενε οτι εχω πει σε αυτο το νημα.

[migf1]

Παιδια να ρωτησω κατι για να μην μπερδευομαστε αδικα?

 

Οταν έχεις ένα loop εμφωλιασμενο το οποιο εκτυπωνει ή γεμιζει εναν δισδιάστατο πινακα

 

η πολυπλοκοτητα του ως προς τις πραξεις και συναρτησει της εισοδου ειναι ή δεν ειναι γραμμική?

 

Σε αυτο θελω ενα ξεκαθαρο ναί ή οχι!!!!  Αφου το δοκιμασα χθες και μονος μου και μαλιστα με VLA στην C

 

με μπερδεψε το ποστ του migf1 υπο την εννοια οτι δεν καταλαβαινω το "εκφρασμενη με ενα μονο loop"...

 

Έχεις εισοδο 16 στοιχεια .... εχεις 16 πραξεις. Δεν υπαρχει καμια μεταβολη ως προς την επιδοση... αρα γραμμικη πολυπλοκοτητα. Μηπως εχω καταλαβει κατι λαθος?

 

Νομίζω μπερδεύεσαι γιατί δεν έχεις ξεκαθαρίσει τι σημαίνει μέγεθος σε context big-oh notation. Όταν αλλάζεις την σύνθεση του μεγέθους του προβλήματος, τότε αλλάζει και το αποτέλεσμα της πολυπλοκότητας.

 

Εσύ λοιπόν μέσα στο ίδιο context προσπαθείς να βγάλεις ίδια την πολυπλοκότητα και όταν το Ν το εκλαμβάνεις ως 16 και όταν το εκλαμβάνεις ως 4. Θα πρέπει να διαλέξεις ένα από τα δυο.

 

Αν επιλέξεις το 2ο (δηλαδή το 4) τότε αναγκαστικά θα πρέπει να εισαγάγεις και δεύτερη παράμετρο στην ποιοτική σύνθεση του μεγέθους, το Μ, προκειμένου να μπορέσεις να εκφράσεις το συνολικό μέγεθος του προβλήματός σου και κατ' επέκταση για να μπορέσεις να αναλύσεις το nested loop. Στην προκειμένη περίπτωση όμως (στο συγκεκριμένο παράδειγμα που δίνεις δηλαδή) το Μ ισούται με Ν (ίσα με 4 και τα δυο) οπότε η πολυπλοκότητα σου βγάζει Ο(Ν^2) ... αντί για Ο(Ν*Μ) που είναι η γενική περίπτωση.

 

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

[bird]

Σκέψου ότι κάποιος σου ζητάει να λύσεις ένα σύστημα εξισώσεων 2x2. Τότε μπορείς να θεωρήσεις ότι για να το λύσεις (με ορίζουσες πχ) χρειάζεσαι έναν πίνακα 2x3 για να αποθηκεύσεις τους συντελεστές των εξισώσεων.

 

Αν πεις οτι το μέγεθος του προβλήματος είναι 2x3=6 (οι συντελεστές των εξισώσεων) τότε η πολυπλοκότητα είναι O(N)

 

Αν όμως θεωρήσεις ότι το μέγεθος του πρβλήματος είναι ο αριθμός των αγνώστων (2 στην συγκεκριμένη περίπτωση) τοτε η πολυπλοκότητα είναι Ο(Ν*(Ν+1)) = Ο(Ν^2)

[Star_Light]

Ναι καταλαβα. Αλλο πραγμα οι διαστάσεις και αλλο τα δεδομένα(στοιχεια) που θα μπουν σε αυτές ειναι διαφορετικα μεγεθη αν κοιταξεις στο χαρτι με μεγεθος 3 γραμμες συνολικα και 3 στηλες έχεις κανει ας πουμε 9 εκχωρησεις αρα οντως ειναι 3^2 αμα το δεις ετσι. Σωστος  ημουν ομως στο οτι δεν σημαινει οτι επειδη εχεις εμφωλιασμενο loop θα εχεις στανταρ και τετραγωνικη πολυπλοκοτητα τουλαχιστον σε τετοιες περιπτωσεις που συζητάμε ακριβως τωρα. Στην εισαγωγή στο διδιάστατο πίνακα αν έχουμε Ν*Ν στοιχεία σαν είσοδο και απλά κάνουμε Ν*Ν εμφανίσεις και θέσουμε Ν*Ν = n ως είσοδο η πολυπλοκότητά θα είναι O(n).

 

Τελοςπαντων οκ... να ρωτησω κατι αλλο στο edit που εκανα με αυτες τις ψιλοαποριουλες.... ειναι ενταξει αυτα που εγραψα? αν μπορει κανεις να τα δει και αν εχει καμια διορθωση οκ. Σας ζαλισα λιγο ε? θα λετε τωρα ε τον μαλεα δεν καταλαβαινει τι του λεμε!!!!

[migf1]

Ναι καταλαβα. Αλλο πραγμα οι διαστάσεις και αλλο τα δεδομένα(στοιχεια) που θα μπουν σε αυτές ειναι διαφορετικα μεγεθη αν κοιταξεις στο χαρτι με μεγεθος 3 γραμμες συνολικα και 3 στηλες έχεις κανει ας πουμε 9 εκχωρησεις αρα οντως ειναι 3^2 αμα το δεις ετσι. Σωστος  ημουν ομως στο οτι δεν σημαινει οτι επειδη εχεις εμφωλιασμενο loop θα εχεις στανταρ και τετραγωνικη πολυπλοκοτητα τουλαχιστον σε τετοιες περιπτωσεις που συζητάμε ακριβως τωρα. Στην εισαγωγή στο διδιάστατο πίνακα αν έχουμε Ν*Ν στοιχεία σαν είσοδο και απλά κάνουμε Ν*Ν εμφανίσεις και θέσουμε Ν*Ν = n ως είσοδο η πολυπλοκότητά θα είναι O(n).

 

Όχι! Εκτός αν εννοείς πως θα έχεις στο τέλος O(n) με n = Ν*Ν (δηλαδή O(N^2)). Άλλο δηλαδή το n κι άλλο το N.

 

Τελοςπαντων οκ... να ρωτησω κατι αλλο στο edit που εκανα με αυτες τις ψιλοαποριουλες.... ειναι ενταξει αυτα που εγραψα? αν μπορει κανεις να τα δει και αν εχει καμια διορθωση οκ. Σας ζαλισα λιγο ε? θα λετε τωρα ε τον μαλεα δεν καταλαβαινει τι του λεμε!!!!

 

Νομίζω αυτές οι απορίες πηγάζουν από το ότι ακόμα δεν έχεις καταλάβει ακριβώς τι παίζει. Δες το link που σου έδωσα αύριο, με καθαρό μυαλό, κάνε και τις ασκήσεις που σου έχει (δίνει και τις λύσεις) κι αν εξακολουθείς να έχεις απορίες, γράψτες εδώ να τις ξαναδούμε.

[AllCowsEatGrass]

Star_Light αν διαβάσεις το ποστ του defacer και καταλάβεις τι λέει θα δεις οτι το 17 δεν είναι τυχαίο νούμερο, είναι πρώτος αριθμός. Δηλαδή δεν ισχύει για έναν οποιοδήποτε δισδιάστατο πίνακα m * n, καθώς το μόνο γινόμενο που ορίζει το 17 έιναι το 1 * 17, αυτό σημαίνει πως ορίζουμε λάθος το πρόβλημα! Διορθώστε με αν κάνω λάθος...

 

 

Ωραίο trick!

 

[bird]

Star_Light αν διαβάσεις το ποστ του defacer και καταλάβεις τι λέει θα δεις οτι το 17 δεν είναι τυχαίο νούμερο, είναι πρώτος αριθμός. Δηλαδή δεν ισχύει για έναν οποιοδήποτε δισδιάστατο πίνακα m * n, καθώς το μόνο γινόμενο που ορίζει το 17 έιναι το 1 * 17, αυτό σημαίνει πως ορίζουμε λάθος το πρόβλημα! Διορθώστε με αν κάνω λάθος...

 

 

Ωραίο trick!

 

 

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

[Star_Light]

Όχι! Εκτός αν εννοείς πως θα έχεις στο τέλος O(n) με n = Ν*Ν (δηλαδή O(N^2)). Άλλο δηλαδή το n κι άλλο το N.

 

 

Νομίζω αυτές οι απορίες πηγάζουν από το ότι ακόμα δεν έχεις καταλάβει ακριβώς τι παίζει. Δες το link που σου έδωσα αύριο, με καθαρό μυαλό, κάνε και τις ασκήσεις που σου έχει (δίνει και τις λύσεις) κι αν εξακολουθείς να έχεις απορίες, γράψτες εδώ να τις ξαναδούμε.

 

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

 

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

 

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

 

Aπλα η πολυπλοκοτητα ειναι μια εννοια που δεν μαθαινεται μεσα σε ενα βραδυ απο οτι καταλαβα.... ουτε καν σε 2 θελει εξασκηση γενικοτερη.

 

p.s Το οχι που παει? στην παρατηρηση του Tasos9 μονο ή σε ολo το μηνυμα μου?