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

Diotima

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

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

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

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

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

 

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Η συζήτηση για την πολυπλοκότητα και την τάξη θα πρέπει να ξεκινάει από το ποια είναι η είσοδος. Στη συνέχεια πρέπει να ξεκαθαρίσουμε ποιο είναι το μέγεθος της εισόδου. Αυτό κανονικά είναι το πλήθος των bits. Μπορεί όμως να είναι κάποιο πολλαπλάσιό του όπως είναι το πλήθος των bytes ή το πλήθος των χαρακτήρων. Το να πάρεις κάποιο πολλαπλάσιο δεν αλλάζει την τάξη του αλγορίθμου, απλά αλλάζει το συντελεστή του μεγιστοβάθμιου όρου. Σαν να αλλάζεις μονάδα μετρήσεως δηλαδή.
Το μέγεθος της εισόδου  θα είναι η ανεξάρτητη μεταβλητή μας. Η πολυπλοκότητα είναι μια συνάρτηση με ανεξάρτητη μεταβλητή το μέγεθος της εισόδου και εξαρτημένη το πλήθος των βημάτων.
Στη ΔΤ2 από ότι καταλαβαίνω είσοδος είναι το πλήθος των στοιχείων του πίνακα (που είναι πολλαπλάσιο των χαρακτήρων που χρειαζόμαστε για να κωδικοποιήσουμε τον ένα αριθμό). Αν είναι λοιπόν το πλήθος των στοιχείων εισόδου είναι ν, η πολυπλοκότητα είναι Ο(ν)
Βέβαια θα έπρεπε να το γράψει
//Δεδομένα donation,ν//
Για ι από 1 μέχρι ν


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

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

kpapad13

  • Νέος
  • *
  • Μηνύματα: 6
Καλησπέρα συνάδελφοι θα ήθελα τη γνώμη σας,

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

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

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

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

dpa2006

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 769
Επειδή δεν μπορώ να το βρω, σε ποιο σημείο αναφέρεται αυτό στο σχολικό βιβλίο;
Βιβλίο Εκπαιδευτικού σελ 132 (138)
ΔΤ1
Παράθεση
Γενικά, ισχύει ότι κάθε απλός βρόχος έχει γραμμική πολυπλοκότητα, κάθε διπλός βρόχος έχει τετραγωνική πολυπλοκότητα κοκ.
Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

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

  • Δεινόσαυρος
  • *****
  • Μηνύματα: 288
Βιβλίο Εκπαιδευτικού σελ 132 (138)
ΔΤ1
Ευχαριστώ πολύ, κοίταξα μόνο το βιβλίο μαθητή και το τετράδιο. Βέβαια λέει γενικά άρα δεν είναι απόλυτο αλλά πράγματι δεν καλύπτει όλες τις περιπτώσεις.  Είναι όμως στην εξεταστέα ύλη ο υπολογισμός αυτός;
Επίσης δεν είχα διαβάσει όλη την συζήτηση όπου προφανώς υπάρχει η απάντηση στο ερώτημα μου.

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Το εφαρμόζει πάντως και στο παράδειγμα 2 (σελ 46) στο τετράδιο μαθητή. Βγάζει τετραγωνικό τον αλγόριθμο ενώ είναι γραμμικός.

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

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

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Το εφαρμόζει σωστά. Ο αλγόριθμος είναι τετραγωνικός.  Αν μέτρησα σωστά οι πράξεις είναι 2n2+4n+4 <=10n2.
Άρα Ο(n2)

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

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

  • Βετεράνος
  • ****
  • Μηνύματα: 63

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
Γι αυτό υπάρχει η διαφωνία. Διαβάζει n^2 στοιχεία οπότε το μέγεθος της εισόδου κατά τη γνώμη μου είναι n^2. Η συνάρτηση f(n^2)=2n^2+4n+4 είναι γραμμική.
Το μέγεθος της εισόδου είναι το πόσα στοιχεία διαβάζει (δες και αυτά που έγραψα στις 10/5 για τα bits και τους χαρακτήρες)

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

  • Βετεράνος
  • ****
  • Μηνύματα: 63
Καταλαβαίνω τι λες αλλά το θέμα είναι καθαρά μαθηματικό και ο μαθηματικός ορισμός βγάζει Ο(n2)
Βρίσκουμε μια συνάρτηση που φράσσει απο πάνω αυτή που έχουμε (ενδεχομένως απο κάποιο σημείο και μετά)

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

gpapargi

  • Γενικός διαχειριστής
  • *****
  • Μηνύματα: 2457
  • I 'm not young enough to know everything
και η f(n2)=2n2+4n+4 δεν είναι γραμμική

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

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

  • Βετεράνος
  • ****
  • Μηνύματα: 63
 f(n)=2n2+4n+4 και για c=3 και n>=5 ισχύει πάντα |f(n)|<=cn2. Αρα η τάξη του αλγορίθμου είναι Ο(n2)