χρόνοι εκτέλεσης αλγορίθμων..

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

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

Απάντηση
jimis86
Δημοσιεύσεις: 4
Εγγραφή: 25 Ιαν 2009 21:46

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από jimis86 » 25 Ιαν 2009 22:05

ψαχνω μια τεμκηριωμενη απαντηση στο ερωτημα που εχει να κανει με ταχυτητες εκτελεσης, συγκεκριμενα ο χρονος 1ου αλγοριθμου ειναι (1/3)n^2+6 και του 2ου 111n-312. ποιο αλγοριθμο θα προτιμουσαμε αν υποθεσουμε οτι οι υπολοιποι παραγοντες ειναι ιδιοι?

Άβαταρ μέλους
Hermeia
Honorary Member
Δημοσιεύσεις: 987
Εγγραφή: 02 Αύγ 2004 00:14
Τοποθεσία: Αθήνα
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από Hermeia » 26 Ιαν 2009 00:11

σε τι τιμές παιζει το ν ?
- βασικά ψάχνεις τη μέγιστη κι ελάχιστη τιμή στο καθένα.. αναλογα με το πεδίο τιμών του ν αλλιώς δεν έχουμε ιδέα..
Hermeia the InfoSharer
Η Γνώση είναι Δύναμη
Εικόνα

jimis86
Δημοσιεύσεις: 4
Εγγραφή: 25 Ιαν 2009 21:46

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από jimis86 » 26 Ιαν 2009 00:14

κοιταξε φιλε μου για τιμες δεν λεει απολυτως τιποτα! αυτο που μου ζηταει ειναι να δικαιολογησω ποιο απο τους 2 θα προτιμουσα (αν και απ οτι καταλαβα ρολο παιζει το ν ή ν^2 και οχι τα άλλα νουμερα.. πρεπει να ειναι πολυ απλη η ερωτηση καθως ειναι θεμα εξετασεων αρα μαλλον δεν χρειαζετε κατι εξηζητημενο.. μια γρηγορη απαντηση θα θελει..

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 00:21

Εξαρτάται από την τιμή του n προφανώς.

Θέτουμε:
F1 = (1/3)n^2+6
F2 = 111n-312

Βάζουμε τις δύο ποσότητες ίσες [F1=F2] και βρίσκουμε για ποιά n είναι ίσες.

Με μια πρόχειρη επίλυση βρίσκουμε
n1 = 2.8899
n2 = 274.6100

Mετά υπολογίζουμε για μια ενδιάμεση τιμή την διαφορά F1-F2.

Δοκιμή για n=10:
[(1/3)n^2+6]-[111n-312] = [(1/3)*10^2+6]-[111*10-312] > 0

Άρα για 2.8899 < n < 274.6100 ο χρόνος F1 είναι μεγαλύτερος του χρόνου F2.
Για τις υπόλοιπες τιμές του n, ο χρόνος F2 είναι μεγαλύτερος του F1.

Mαθηματικά λυκείου ;)

Yγ1: Αν έκανα σωστά τις πράξεις...

Υγ2: Τεκμηρίωση μην περιμένεις...
Σου έδωσα την λύση, την τεκμηρίωση βρες την μόνος σου, στο βιβλίο της 3ης λυκείου έχει δεκάδες τέτοιες ασκήσεις που απλά στηρίζονται στην επίλυση μιας δευτεροβάθμιας και την συμπεριφορά της συνάρτησης [αύξουσα-φθίνουσα, σε εκείνα τα κεφάλαια]

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 00:32

Επειδή σκυλοβαριέμαι, θα πω 2 πραγματάκια ακόμα.

Η διαφορά F1-F2 είναι μια καθαρή a*x^2+bx+c

Όταν την μηδενίζουμε είναι μια δευτεροβάθμια εξίσωση.

Έχει λοιπόν 2 ρίζες [φανταστικές, μιγαδικές ή πραγματικές]. Κατά την επίλυση η Διακρίνουσα είναι θετική, άρα οι ρίζες είναι πραγματικές [τις βρήκα πριν].

Μιλάμε για μια παραβολή[?] η οποιά μηδενίζει το Y [τέμνει τον άξονα Χ] 2 φορές...

Άρα το ενδιάμεσο κομμάτι θα είναι θετικό [ή αρνητικό] και όλο το υπόλοιπο αρνητικό [ή θετικό].

Αυτά...

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 00:36

Ξαναβαριέμαι!

Αφού το ενδιάμεσο τμήμα είναι θετικό, παρουσιάζει τοπικό [και γενικό] μέγιστο, το οποίο προκύπτει στο σημείο που μηδενίζεται η παράγωγος του F1-F2.

H παράγωγος είναι (2/3)n-111.

Μηδενίζεται για n = 166.5

Άρα η συνάρτηση της διαφοράς που εξετάζουμε είναι γνησίως αύξουσα για n<166.5 και γνησίως φθίνουσα για n>166.5

Yγ: Κάπου έχω κάνει λάθος στις πράξεις, στάνταρ! :(

jimis86
Δημοσιεύσεις: 4
Εγγραφή: 25 Ιαν 2009 21:46

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από jimis86 » 26 Ιαν 2009 00:49

με τον προγραμματισμο τι σχέση εχουν ομως αυτα? γιατι πιστευω οτι καπου υπαρχει μια θεωρια γυρω απο την ταχυτητα λογαριθμων σε σχεση με το ν...

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από dva_dev » 26 Ιαν 2009 00:58

Τι σημαίνει "αρνητικός χρόνος" (στον 2ο αλγόριθμο για n<3);
Τι συμβαίνει αν εκτελεστεί ο αλγόριθμος; Θα γυρίσει ο χρόνος πίσω;

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 11:02

@jimis86 O προγραμματισμός είναι 99% μαθηματικά. Εγώ σου έδωσα την θεωρία που σου χρειάζεται.

@dva_dev Δεν βρήκα πουθενά αρνητικό χρόνο. Βρήκα αρνητική διαφορά.
Όταν βρήκα αρνητική τιμή, σημαίνει ότι ο χρόνος F1 είναι μικρότερος από τον F2.

Δεν ανέλυσα το πεδίο ορισμού του n γιατί πολύ απλά δεν ξέρω τι είναι!
Ο χρόνος της πρώτης είναι ορισμένος ως F1(n) και της δεύτερης F2(n)

chief
Δημοσιεύσεις: 49
Εγγραφή: 14 Οκτ 2008 13:37
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από chief » 26 Ιαν 2009 11:46

Η πρώτη είναι μεγαλύτερης τάξις μεγέθους λόγο n^2. γενικά το n είναι μικρότερης τάξης μεγέθους από το n^2.

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 12:24

Nαι, είναι δεύτερης τάξης η F1 κι η F2 είναι πρώτης τάξης!

Αλλά αυτό πού κολλάει;

Άβαταρ μέλους
dva_dev
Script Master
Δημοσιεύσεις: 3790
Εγγραφή: 16 Σεπ 2005 01:32
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από dva_dev » 26 Ιαν 2009 12:48

Eneme έγραψε:Δεν βρήκα πουθενά αρνητικό χρόνο.
F2(n) = 111n-312
Για τιμές
n=0 -> F2(0)= -312 (min/sec/... ή οποιαδήποτε είναι η μονάδα μέτρησης του χρόνου)
n=1 -> F2(1)= -201
n=2 -> F2(2)= -90

Τι σημβαίνει όταν εκτελέσω τον 2ο αλγόριθμο με πλήθος στοιχείων (0,1,2);
Τι σημαίνουν οι αρνητικοί χρόνοι;

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 15:41

Δεν ασχολήθηκα με τα πεδία ορισμού των συναρτήσεων είναι η αλήθεια!

Όντως, αυτό που λες εκφράζεται γενικά ως εξής:
F1>0 ισχύει για κάθε n ως άθροισμα θετικών αριθμών
F2>0 => 111n-312>0 => 111n>312 => n>2.8108

Aυτό θα πρέπει να τύχει συναλήθευσης με όσα έχω ήδη αναλύσει!

Άρα για n<2.8108 θα πρέπει να βγαίνει μήνυμα σφάλματος!


Άρα και με το δικό σου λιθαράκι, η άσκηση έχει λυθεί εξαντλητικά αναλυτικά.

Η "μετάφραση" σε εντολές ας γίνει από τον ενδιαφερόμενο!

Άβαταρ μέλους
soteres2002
S. & H. Moderator
Δημοσιεύσεις: 1524
Εγγραφή: 05 Μαρ 2004 22:17
Τοποθεσία: Ιωάννινα

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από soteres2002 » 26 Ιαν 2009 19:36

Καλύτερα δείτε πιο εμπειρικά και γενικά το ζήτημα (δηλ. με το στυλ που προσεγγίζουμε τέτοια προβλήματα, βλ. ασυμπτωτική ανάλυση). Αυτά με τις τιμές του n είναι γενικά μικρής σημασίας, εκτός απο μερικές περιπτώσεις, αλλά γενικά δεν ασχολούμαστε με τέτοιες λεπτομέρειες όταν κάνουμε μια γενική προτίμηση ανάμεσα σε αλγορίθμους. Προφανώς η συνάρτηση n^2 δεν θα προτιμηθεί από την γραμμική, καθώς για μεγάλες τιμές του n F(n^2) >> F(n). Αυτή είναι μια πολύ τεκμηριωμένη απάντηση για το ποιον αλγοριθμο θα επιλέξουμε, και δεν χρειάζονται περαιτέρω φορμαλισμοί και αναλύσεις. Αν το εξειδικεύσεις περισσότερο, η απάντηση δεν είναι γενική αλλά το ερώτημα εξειδικεύεται απο κει και πέρα. Επίσης, αν το δούμε και καθαρά υποκειμενικά και γενικά το ερώτημα, ο τετραγωνικός αλγόριθμος είναι πολύ μάπα σε σχέση με τον γραμμικό, αφού δεν έχει καλή απόδοση για μεγαλύτερο εύρος του n εκτός από τα μικρά διαστήματα της εισόδου που αποδίδει καλύτερα. Πάρτε πχ τιμές του n ξεκινώντας από 200000 και συνεχίστε με βήμα 50000 και θα δείτε την τραγική διαφορά στην πολυπλοκότητα (χρόνου, διαστήματος, οτιδήποτε άλλο). Αν μας ενδιέφεραν περισσότερο μικρές τιμές του ν στον πραγματικό κόσμο, δεν θα υπήρχε λόγος να σχεδιάζονται αποδοτικότεροι αλγόριθμοι αφού και για τις μικρές τιμές των κακών σε απόδοση ασυμπτωτικά (για μεγάλα ν δλδ) αλγορίθμων θα πέρναμε ικανοποιητικά αποτελέσματα.

Άβαταρ μέλους
EneMe
Super Moderator
Δημοσιεύσεις: 13307
Εγγραφή: 09 Ιούλ 2002 13:29
Τοποθεσία: Στο κέντρο της Ελλάδας!
Επικοινωνία:

χρόνοι εκτέλεσης αλγορίθμων..

Δημοσίευση από EneMe » 26 Ιαν 2009 20:09

Όταν ορίζεις μια F(n^2) που εδώ έχει την μορφή Α(n^2) + B, ουσιαστικά την μετατρέπεις σε πρωτοβάθμια του της μορφής F(x)=Ax+B με ένα όρισμα x=n^2.

Είναι σαν ενα τύπο που είχε συνηθίσει να χρησιμοποιεί της SQRT(x) κι όταν έψαχνε να βρει κυβική ρίζα, δεν σκέφτηκε το πολύ απλό n^(1/3).

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

Απάντηση

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

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

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