Δημοσιεύτηκε: 12 Οκτ 2011, 01:58
sokoban4ever έγραψε:@Star_Light
Για την προπροηγούμενη δήλωση ..(κάπου έκει)...
Για κάθε εμφωλεμένο loop έχεις και συν ένα στην δύναμη της "χρονική πολυπλοκότητα" του αλγόρυθμου σου
αν κάθε επανάληψη σε κάθε for είναι ισάρυθμη...
πχ το παρακάτω είναι της τάξης n^3
- Κώδικας: Επιλογή όλων
for ... {α}
for ... {β}
for ...{γ}
Σημείωση:
Αν το α=β=γ τότε ο αλγόριθμος έχει πολυπλοκότητα n^3
σε άλλες περιπτώσεις πρέπει να υπολογίζεις τους χρόνους συνθέτωντας ένα πολυώνυμο των χρόνων των μεταβλητών...
στο τέλος εκείνο που χαρακτηρίζει τον βαθμό χρονικής πολυπλοκότητας του αλγορίθμου είναι
είναι η μέγιστη τάξη (δύναμη) του πολυώνυμου που θα "βγάλεις" αναλύοντας βήμα βήμα τον αλγόριθμο ( απο τον κώδικα)
Μια ωραία εξήγηση έχει εδώ στο stackoverflow
http://stackoverflow.com/questions/3255 ... 66#4852666
Φιλικά
Αν έχεις κάποιο χειρόγραφο πανεπιστημιακό παράδειγμα θα με ενδιέφερε να βγάλουμε μια πολυπλοκότητα
που δεν έχει ίσα τα α=β=γ που λες εξαρχής. Ειπαμε τα α=β=γ καθε ενα απο αυτα ειναι το πλήθος των επαναλήψεων της
κάθε λούπας έτσι?
