Χρόνος εκτέλεσης

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

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Άβαταρ μέλους
pasxal
Δημοσιεύσεις: 83
Εγγραφή: 16 Απρ 2010 04:39

Χρόνος εκτέλεσης

Δημοσίευση από pasxal » 10 Σεπ 2010 08:59

Έστω ότι έχω αυτό το τμήμα κώδικα.

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

for &#40;i=1; i<=N; i++&#41;&#123;
   y&#91;i&#93;=0;	
   for &#40;j=1; j<=N; j++&#41; 
        y&#91;i&#93;=y&#91;i&#93;+A&#91;i&#93;&#91;j&#93;*x&#91;j&#93;; 
&#125;
Μπορεί κάποιος να μου εξηγήσει πως προκύπτει ο ασυμπτωτικός χρόνος εκτέλεσης;

nbc
Honorary Member
Δημοσιεύσεις: 526
Εγγραφή: 05 Σεπ 2009 20:12
Επικοινωνία:

Χρόνος εκτέλεσης

Δημοσίευση από nbc » 10 Σεπ 2010 11:33

Εκφράζεις το χρόνο εκτέλεσης του αλγορίθμου:

f(n) = c1*n + c2*n^2

όπου

- c1 ο χρόνος εκτέλεσης του εξωτερικού βρόγχου
- c2 ο χρόνος εκτέλεσης του εσωτερικού


Για να μετατρέψεις τον συμβολισμό f(n) σε big-O, απλοποιείς με βάση δύο κανόνες:

- Στα αθροίσματα κρατάς τον μεγαλύτερο (high-order) όρο
- Στα γινόμενα αγνοείς τις σταθερές

ή (ανάποδα)

- Πετάς τις σταθερές
- Κρατάς το μεγαλύτερο όρο

* Ο λόγος είναι ότι οσο το n τείνει στο άπειρο, οι τιμές των σταθερών και των όρων μικρής τάξης επηρρεάζουν ολοένα και λιγότερο το αποτέλεσμα.

Συνεπώς, με βάση τα παραπάνω, η συνάρτησή σου είναι κλασσική quadratic: O(n^2).

Άβαταρ μέλους
pasxal
Δημοσιεύσεις: 83
Εγγραφή: 16 Απρ 2010 04:39

Χρόνος εκτέλεσης

Δημοσίευση από pasxal » 10 Σεπ 2010 12:30

Ευχαριστώ πολύ φίλε γιατί το βιβλίο που διαβάζω δν το έχει το θέμα.

Αυτό ισχύει μονο για βρόχους ή και για άλλες δομές;

nbc
Honorary Member
Δημοσιεύσεις: 526
Εγγραφή: 05 Σεπ 2009 20:12
Επικοινωνία:

Χρόνος εκτέλεσης

Δημοσίευση από nbc » 10 Σεπ 2010 13:14

Ισχύει για οποιονδήποτε αλγόριθμο.

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

ΠΧ: function increment(n){return n+1;}

f(n) = c = O(1)

Άβαταρ μέλους
pasxal
Δημοσιεύσεις: 83
Εγγραφή: 16 Απρ 2010 04:39

Χρόνος εκτέλεσης

Δημοσίευση από pasxal » 10 Σεπ 2010 13:18

Και σε περίπτωση που μπορούν να παραληφθούν κάποια βήματα ενός αλγορίθμου;
Δλδ σε περίπτωση if.

nbc
Honorary Member
Δημοσιεύσεις: 526
Εγγραφή: 05 Σεπ 2009 20:12
Επικοινωνία:

Χρόνος εκτέλεσης

Δημοσίευση από nbc » 10 Σεπ 2010 13:30

Μας ενδιαφέρει ο μέγιστος χρόνος εκτέλεσης. Το worst case scenario. Συνεπώς, αν ο χρόνος εκτέλεσης εξαρτάται από συνθήκη, εμείς λαμβάνουμε υπόψη τη χειρότερη περίπτωση (όσον αφορά χρόνο, μνήμη, CPU, κλπ).

Άβαταρ μέλους
pasxal
Δημοσιεύσεις: 83
Εγγραφή: 16 Απρ 2010 04:39

Χρόνος εκτέλεσης

Δημοσίευση από pasxal » 10 Σεπ 2010 13:32

Ναι αυτό το είχα ξεχάσει.
Ευχαριστώ πολύ για την βοήθεια.

Απάντηση

Επιστροφή στο “γλώσσες προγραμματισμού - γενικά”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες