Θέμα: Υπολογισμός χρόνου εκτέλεσης (υπολογισμός αριθμού πράξεων των εντολών)

[Diotima]

Ο κανόνας "Γενικά, ισχύει ότι κάθε απλός βρόχος έχει γραμμική πολυπλοκότητα, κάθε διπλός βρόχος έχει τετραγωνική πολυπλοκότητα κοκ." δεν ισχύει όμως όταν οι βρόχοι έχουν σταθερό αριθμό επαναλήψεων. Την απάντηση στη ΔΤ2 δεν την είχα προσέξει, έχει σταθερό βρόχο με 30 επαναλήψεις και απαντά λάθος ότι η πολυπλοκότητα είναι Ο(n) ενώ είναι Ο(1). Η εκφώνηση της άσκησης δε αναφέρει κάποιο σταθερό πλήθος μαθητών, αναφέρει "τους μαθητές της τάξης σας" οπότε σου λέει αποκλείεται να είναι πάνω από 30, αυτό νομίζω ότι σκέφτηκε. Ένας μαθητής θα την έλυνε ίσως με το πραγματικό πλήθος των μαθητών της τάξης του.

Πάντως το συμπέρασμα που βγάζω από τις απαντήσεις της ΔΣ1 και της ΔΤ2 είναι ότι όποιος ή όποιοι απάντησαν εφαρμόζουν λάθος τον παραπάνω κανόνα σε βρόχους με σταθερό πλήθος επαναλήψεων.

[Λάμπρος Παπαδόπουλος]

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

Σωστά. Γι΄αυτό είπα ότι τον χρησιμοποιούν λανθασμένα.
Όσο για το ΔΤ2 η απάντηση είναι σωστή. Η αντίρρησή μου είναι οτι στην απάντηση χρησιμοποιεί ένα στιγμιότυπο του προβλήματος (30 μαθητές) για να απαντήσει για τη γενική περίπτωση ( n μαθητές ).

 

[gpapargi]

Η συζήτηση για την πολυπλοκότητα και την τάξη θα πρέπει να ξεκινάει από το ποια είναι η είσοδος. Στη συνέχεια πρέπει να ξεκαθαρίσουμε ποιο είναι το μέγεθος της εισόδου. Αυτό κανονικά είναι το πλήθος των bits. Μπορεί όμως να είναι κάποιο πολλαπλάσιό του όπως είναι το πλήθος των bytes ή το πλήθος των χαρακτήρων. Το να πάρεις κάποιο πολλαπλάσιο δεν αλλάζει την τάξη του αλγορίθμου, απλά αλλάζει το συντελεστή του μεγιστοβάθμιου όρου. Σαν να αλλάζεις μονάδα μετρήσεως δηλαδή.
Το μέγεθος της εισόδου  θα είναι η ανεξάρτητη μεταβλητή μας. Η πολυπλοκότητα είναι μια συνάρτηση με ανεξάρτητη μεταβλητή το μέγεθος της εισόδου και εξαρτημένη το πλήθος των βημάτων.
Στη ΔΤ2 από ότι καταλαβαίνω είσοδος είναι το πλήθος των στοιχείων του πίνακα (που είναι πολλαπλάσιο των χαρακτήρων που χρειαζόμαστε για να κωδικοποιήσουμε τον ένα αριθμό). Αν είναι λοιπόν το πλήθος των στοιχείων εισόδου είναι ν, η πολυπλοκότητα είναι Ο(ν)
Βέβαια θα έπρεπε να το γράψει
//Δεδομένα donation,ν//
Για ι από 1 μέχρι ν
…

Αλλά δεν μπορεί να εννοεί κάτι άλλο αφού αν έδινε πχ 50 στοιχεία δε θα ήταν σωστό το
«Για ι από 1 μέχρι 30». Σε αυτή την περίπτωση θα έγραφε τότε «Για ι από 1 μέχρι 50».

Αυτό που λέει το βιβλίο ότι  διπλός βρόχος = τετραγωνική πολυπλοκότητα και μονός βρόχος = γραμμική πολυπλοκότητα, είναι κάπως ελαφρύ. Πχ μπορώ να διαβάσω  100 στοιχεία και να τα αποθηκεύσω σε δισδιάστατο πίνακα 10Χ10 ή σε μονοδιάστατο πίνακα 100 θέσεων. Δεν μπορεί να κάνω τα ίδια βήματα και στη μια να έχω τετραγωνική και στην άλλη γραμμική πολυπλοκότητα. Δεν έχει ληφθεί υπόψη η είσοδος και το μέγεθος εισόδου δηλαδή η ανεξάρτητη μεταβλητή μου. Η συζήτηση χωρίς αυτό είναι στον αέρα.
Αυτό που λέει το βιβλίο ισχύει για το πλήθος των επαναλήψεων. Αυτό δεν έχει να κάνει απαραίτητα με το μέγεθος εισόδου αφού μπορεί ένας διπλός βρόχος να μην επεξεργάζεται στοιχεία εισόδου.

[kpapad13]

Καλησπέρα συνάδελφοι θα ήθελα τη γνώμη σας,

Στην εντολή Γράψε α, β + γ πόσες πράξεις έχουμε;  Είναι 2 (1 για την πρόσθεση και 1 για την έξοδο ) ή 3 (1 για την πρόσθεση , 1 για την έξοδο του α και 1 για την έξοδο του β+γ ); Ελπίζω αν πέσει κάτι τέτοιο να γίνεται η έξοδος κάθε πληροφορίας με διαφορετική εντολή...

[Αθανάσιος Πέρδος]

Αυτό που λέει το βιβλίο ότι  διπλός βρόχος = τετραγωνική πολυπλοκότητα και μονός βρόχος = γραμμική πολυπλοκότητα, είναι κάπως ελαφρύ. Πχ μπορώ να διαβάσω  100 στοιχεία και να τα αποθηκεύσω σε δισδιάστατο πίνακα 10Χ10 ή σε μονοδιάστατο πίνακα 100 θέσεων. Δεν μπορεί να κάνω τα ίδια βήματα και στη μια να έχω τετραγωνική και στην άλλη γραμμική πολυπλοκότητα. Δεν έχει ληφθεί υπόψη η είσοδος και το μέγεθος εισόδου δηλαδή η ανεξάρτητη μεταβλητή μου. Η συζήτηση χωρίς αυτό είναι στον αέρα.
Αυτό που λέει το βιβλίο ισχύει για το πλήθος των επαναλήψεων. Αυτό δεν έχει να κάνει απαραίτητα με το μέγεθος εισόδου αφού μπορεί ένας διπλός βρόχος να μην επεξεργάζεται στοιχεία εισόδου.

Επειδή δεν μπορώ να το βρω, σε ποιο σημείο αναφέρεται αυτό στο σχολικό βιβλίο;

[dpa2006]

Επειδή δεν μπορώ να το βρω, σε ποιο σημείο αναφέρεται αυτό στο σχολικό βιβλίο;

Βιβλίο Εκπαιδευτικού σελ 132 (138)
ΔΤ1

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

[Αθανάσιος Πέρδος]

Βιβλίο Εκπαιδευτικού σελ 132 (138)
ΔΤ1

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

[gpapargi]

Το εφαρμόζει πάντως και στο παράδειγμα 2 (σελ 46) στο τετράδιο μαθητή. Βγάζει τετραγωνικό τον αλγόριθμο ενώ είναι γραμμικός.

[Λάμπρος Παπαδόπουλος]

Το εφαρμόζει πάντως και στο παράδειγμα 2 (σελ 46) στο τετράδιο μαθητή. Βγάζει τετραγωνικό τον αλγόριθμο ενώ είναι γραμμικός.

Το εφαρμόζει σωστά. Ο αλγόριθμος είναι τετραγωνικός.  Αν μέτρησα σωστά οι πράξεις είναι 2n²+4n+4 <=10n².
Άρα Ο(n²)

[gpapargi]

Το εφαρμόζει σωστά. Ο αλγόριθμος είναι τετραγωνικός.  Αν μέτρησα σωστά οι πράξεις είναι 2n²+4n+4 <=10n².
Άρα Ο(n²)

Ποιο είναι το μέγεθος της εισόδου;

[Λάμπρος Παπαδόπουλος]

Ποιο είναι το μέγεθος της εισόδου;

n

[gpapargi]

Γι αυτό υπάρχει η διαφωνία. Διαβάζει n^2 στοιχεία οπότε το μέγεθος της εισόδου κατά τη γνώμη μου είναι n^2. Η συνάρτηση f(n^2)=2n^2+4n+4 είναι γραμμική.
Το μέγεθος της εισόδου είναι το πόσα στοιχεία διαβάζει (δες και αυτά που έγραψα στις 10/5 για τα bits και τους χαρακτήρες)

[Λάμπρος Παπαδόπουλος]

Καταλαβαίνω τι λες αλλά το θέμα είναι καθαρά μαθηματικό και ο μαθηματικός ορισμός βγάζει Ο(n²)
Βρίσκουμε μια συνάρτηση που φράσσει απο πάνω αυτή που έχουμε (ενδεχομένως απο κάποιο σημείο και μετά)

και η f(n²)=2n²+4n+4 δεν είναι γραμμική

[gpapargi]

και η f(n²)=2n²+4n+4 δεν είναι γραμμική

Προφανώς είναι μαθηματικό το θέμα. Η f(n^2) είναι σύνθετη συνάρτηση. Ποιος είναι ο τύπος για το f(n);

[Λάμπρος Παπαδόπουλος]

 f(n)=2n²+4n+4 και για c=3 και n>=5 ισχύει πάντα |f(n)|<=cn². Αρα η τάξη του αλγορίθμου είναι Ο(n²)