Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Πείτε μας με τι πολυπλοκότητα το λύσατε, ή ακόμη κι αν δεν το λύσατε ακόμη.
Μπορείτε να αλλάξετε την ψήφο σας, πχ. σε περίπτωση που βρείτε πιο γρήγορο αλγόριθμο.
Μπορείτε να αλλάξετε την ψήφο σας, πχ. σε περίπτωση που βρείτε πιο γρήγορο αλγόριθμο.
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
O(n^2) worst-case
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
εγώ ρε γαμώτο έχω κολήσει με αυτην τη βλακεία.... χ)
αν μπορει καποιος να help εμενά ας μου στειλει πρωσοπικο μυνημα....
ελπιζω να μην παραβιαζω τους κανόνες..
αν μπορει καποιος να help εμενά ας μου στειλει πρωσοπικο μυνημα....
ελπιζω να μην παραβιαζω τους κανόνες..
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
ιδού και οι καμπύλες πολυπλοκότητας
μπλε->Ο(Ν!)
πράσινο-> Ο(2^Ν)
πορτοκαλί-> Ο(Ν^3)
και (αν υφίσταται)
ροζ-> Ο(Ν^2)
στον άξονα των x είναι ο αριθμός των πόλεων και στον y η πολυπλοκότητα
σχόλια:
1)κατά τη γνώμη μου Ο(Ν^2) δεν μπορεί να υπάρξει, φαίνεται κ από τη διαφορά π χει από όλες τις υπόλοιπες καμπύλες...
2)όποιος έχει βρει πολυπλοκότητα Ο(Ν!) να κάτσει να ψάξει για μια από τις άλλες 2
[vlakia]
3)οι πολυπλοκότητες Ο(2^Ν) και Ο(Ν^3) δεν έχουν τόοσο τεράστια διαφορά πια κ μάλιστα μέχρι τις 10 περίπου πόλεις η Ο(2^Ν) είναι γρηγορότερη[/vlakia]
Τελευταία επεξεργασία από το μέλος Ελεύθεροσκοπευτής την Παρ Μαρ 13, 2009 7:07 pm, έχει επεξεργασθεί 1 φορά συνολικά.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Δε τίθεται θέμα σύγκρισης 2^Ν με Ν^3 σε καμία περίπτωση... Καταρχήν η 2^Ν είναι εκθετική και Ν^3 πολυωνυμική... Μόνο αυτό είναι αρκετό για να συμπεραίνουμε ότι ειναι ΠΟΛΥ ΠΟΛΥ πιο αργή η 2^Ν. Το λάθος που κάνεις είναι οτι εξετάζεις ένα ΥΠΕΡΒΟΛΙΚΑ μικρό εύρος τιμών... Τι συμπέρασμα μπορούμε να βγάλουμε για τη συμπεριφορά της συνάρτησης ότι η μέγιστη τιμή που απεικονίζεται είναι 2800 και ο υπολογιστής εκτελεί 1000000000 πράξεις το δευτερόλεπτο??
Μια καλή 2^Ν δεν μπορεί να τα καταφέρει εντός 5 δευτερολέπτων για Ν>23 . Για Ν=40 θα χρειαζόταν περίπου 3 ώρες (χωρις άλλες πράξεις). Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.
Αντίθετα η Ν^3 για Ν=200 χρειάζεται 0.08 δευτερόλεπτα...
Εκεί που δεν υπάρχει ουσιαστική διαφορά για νούμερα μικρότερο του 200 είναι μεταξύ της Ν^2 και της Ν^3. Δε μπορώ να καταλάβω πως μπορεί να αποτελέσει επιχείρημα κατά της ύπαρξης της το ότι Ν^2 είναι πολύ γρήγορη.... Με την ίδια λογική δεν θα έπρεπε να υπάρχει κανέναν αλγόριθμος shortest path αφού είναι πολύ πιο γρήγορος απο τον bruteforce Ν!.
Μπορεί στα νούμερα η 2^Ν να φαίνεται πιο γρήγορη απο την Ν^3 αλλά δεν είναι λόγω της χρήσης στοίβας για την υλοποίησης της 2^Ν.
Γενικώς πάντως έχω την εντύπωση οτι η 2^Ν είναι πιο εύκολη στην υλοποίηση απο την Ν!.
Μια καλή 2^Ν δεν μπορεί να τα καταφέρει εντός 5 δευτερολέπτων για Ν>23 . Για Ν=40 θα χρειαζόταν περίπου 3 ώρες (χωρις άλλες πράξεις). Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.
Αντίθετα η Ν^3 για Ν=200 χρειάζεται 0.08 δευτερόλεπτα...
Εκεί που δεν υπάρχει ουσιαστική διαφορά για νούμερα μικρότερο του 200 είναι μεταξύ της Ν^2 και της Ν^3. Δε μπορώ να καταλάβω πως μπορεί να αποτελέσει επιχείρημα κατά της ύπαρξης της το ότι Ν^2 είναι πολύ γρήγορη.... Με την ίδια λογική δεν θα έπρεπε να υπάρχει κανέναν αλγόριθμος shortest path αφού είναι πολύ πιο γρήγορος απο τον bruteforce Ν!.
Μπορεί στα νούμερα η 2^Ν να φαίνεται πιο γρήγορη απο την Ν^3 αλλά δεν είναι λόγω της χρήσης στοίβας για την υλοποίησης της 2^Ν.
Γενικώς πάντως έχω την εντύπωση οτι η 2^Ν είναι πιο εύκολη στην υλοποίηση απο την Ν!.
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Τα είπε όλα ο Νίκος, δεν έχω να προσθέσω τίποτα.
-
- Δημοσιεύσεις: 33
- Εγγραφή: Πέμ Ιαν 29, 2009 1:57 am
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
οκ, με πεισες, απλά τραγικό λάθος μουthelastnicholas έγραψε:Δε τίθεται θέμα σύγκρισης 2^Ν με Ν^3 σε καμία περίπτωση... Καταρχήν η 2^Ν είναι εκθετική και Ν^3 πολυωνυμική... Μόνο αυτό είναι αρκετό για να συμπεραίνουμε ότι ειναι ΠΟΛΥ ΠΟΛΥ πιο αργή η 2^Ν. Το λάθος που κάνεις είναι οτι εξετάζεις ένα ΥΠΕΡΒΟΛΙΚΑ μικρό εύρος τιμών... Τι συμπέρασμα μπορούμε να βγάλουμε για τη συμπεριφορά της συνάρτησης ότι η μέγιστη τιμή που απεικονίζεται είναι 2800 και ο υπολογιστής εκτελεί 1000000000 πράξεις το δευτερόλεπτο??
Μια καλή 2^Ν δεν μπορεί να τα καταφέρει εντός 5 δευτερολέπτων για Ν>23 . Για Ν=40 θα χρειαζόταν περίπου 3 ώρες (χωρις άλλες πράξεις). Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.
Αντίθετα η Ν^3 για Ν=200 χρειάζεται 0.08 δευτερόλεπτα...
έχεις απολυτο δίκιο
οκ, δεν είναι το βασικό επιχείρημα, αλλά μαθηματικά δεν μπορώ εγώ να καταλαβω (καλά, ουτ αυτό ειν επιχείρημα βασικά) πως θα γινόταν ένα πρόγραμμα σε ν^2, δηλαδή μιλάμε για 2 αντικείμενα π μπορούν να πάρουν ν διαφορετικές τιμές το καθένα; δεν μπορώ να σκευτώ πως θα μοιάζει ο αλγόριθμος...thelastnicholas έγραψε: Εκεί που δεν υπάρχει ουσιαστική διαφορά για νούμερα μικρότερο του 200 είναι μεταξύ της Ν^2 και της Ν^3. Δε μπορώ να καταλάβω πως μπορεί να αποτελέσει επιχείρημα κατά της ύπαρξης της το ότι Ν^2 είναι πολύ γρήγορη.... Με την ίδια λογική δεν θα έπρεπε να υπάρχει κανέναν αλγόριθμος shortest path αφού είναι πολύ πιο γρήγορος απο τον bruteforce Ν!.
όχι ρε συ η ν! βγαίνει με μερικά φορ, η άλλη 2^ν είναι πιο περίπλοκη στην υλοποίησηthelastnicholas έγραψε: Μπορεί στα νούμερα η 2^Ν να φαίνεται πιο γρήγορη απο την Ν^3 αλλά δεν είναι λόγω της χρήσης στοίβας για την υλοποίησης της 2^Ν.
Γενικώς πάντως έχω την εντύπωση οτι η 2^Ν είναι πιο εύκολη στην υλοποίηση απο την Ν!.
-
- Site Admin
- Δημοσιεύσεις: 381
- Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
- Τοποθεσία: Αθήνα
- Επικοινωνία:
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Ορίστε το σωστό plot, χωρίς όμως την N!, γιατί με αυτήν αυξάνεται τόσο πολύ, που κάνει τα άλλα να μην φαίνονται.
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Παιδιά εγώ το έλυσα με πολυπλοκότητα Ο(Ν)
Ας μου πει κάποιος αν ξέρει πόσο είναι το πλήθος των σημείων στο 3ο αρχείο (κρυφό),
γιατί και στα 3 testcases τελειώνω με χρόνο 0.000 sec.
Ας μου πει κάποιος αν ξέρει πόσο είναι το πλήθος των σημείων στο 3ο αρχείο (κρυφό),
γιατί και στα 3 testcases τελειώνω με χρόνο 0.000 sec.
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
άμα έχεις Ο(Ν) πολυπλοκότητα τι σε νοιάζει το μέγεθος των αρχείων?? Αν και τέσταρε το πρόγραμμά σου με το hellenico, γιατί εδώ υπάρχουν αμφιβολίες για λύση με πολυπλοκότητα Ο(Ν^2) πόσο μάλλον για Ο(Ν) !
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Πες μου λίγο, τι είναι αυτό το hellenico?
Κοίτα τι γίνεται, αυτοί έχουν ένα site για δοκιμές άμα είδες, που ό,τι και να βάλεις (π.χ. 50 σημεία)
το βγάζει σχεδόν αμέσως. Ε, τέτοια ταχύτητα έχει και το δικό μου. Ό,τι έβαζα εκεί (στο site)
το δοκίμαζα και στο πρόγραμμά μου και μου έβγαζε την ίδια λύση σχεδόν αμέσως.
Κοίτα τι γίνεται, αυτοί έχουν ένα site για δοκιμές άμα είδες, που ό,τι και να βάλεις (π.χ. 50 σημεία)
το βγάζει σχεδόν αμέσως. Ε, τέτοια ταχύτητα έχει και το δικό μου. Ό,τι έβαζα εκεί (στο site)
το δοκίμαζα και στο πρόγραμμά μου και μου έβγαζε την ίδια λύση σχεδόν αμέσως.
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Δοκίμασε να χρησιμοποιήσεις αυτόν http://www.pdpforum.eu.org/forum/viewto ... 1003#p1003 ή αυτόν http://www.pdpforum.eu.org/forum/viewto ... 1030#p1030 τον testcase maker. Αν έστω σε ένα testcase σου βγάλει λάθος, η λύση σου είναι λάθος. Κάνε γρήγορα γιατι οι υποβολές τελειώνουν το βράδυ.
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Ενδιαφέρον...
Τι αποτέλεσμα βγάζεις στο αρχειο που έχω επισυνάψει?
!!Διορθωση αρχειου!!
Τι αποτέλεσμα βγάζεις στο αρχειο που έχω επισυνάψει?
!!Διορθωση αρχειου!!
- Συνημμένα
-
- evripos.in.txt
- ΤΕΣΤΚΑΣΕ
- (815 Ψηφιολέξεις) Μεταφορτώθηκε 525 φορές
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
μήπως ξέρει κανείς η λύση Ο(2^ν) πόσο χρόνο κάνει στα 200 λιμάνια? Ναι hambos αυτό το site εννοούσα για να τεστάρεις το πρόγραμμά σου. Αν τα έχεις καταφέρει μπράβο.
Τελευταία επεξεργασία από το μέλος georgeha98 την Κυρ Μαρ 15, 2009 6:02 pm, έχει επεξεργασθεί 1 φορά συνολικά.
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
ρε, έλεος, αυτό το αρχείο που έβαλες δεν τα έχει ταξινομημένα, περίμενε να τα ταξινομήσω και
θα σου πω
θα σου πω
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Τα αρχεία που θα δίνονται στο διαγωνισμό δεν θα είναι όλα ταξινομημένα.
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
τα testcases είναι όλα ταξινομημένα. δεν είναι? νομίζω το λέει
-
- Δημοσιεύσεις: 74
- Εγγραφή: Παρ Φεβ 13, 2009 8:07 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Το έχουμ πει. Για την 2^Ν
Δεν αναφέρεται κάπου οτι τα αρχεία ειναι ταξινομημένα. Το ξανα-επισυναψα ταξινομημένα όμως.Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.
- Συνημμένα
-
- evripos.in1.txt
- (816 Ψηφιολέξεις) Μεταφορτώθηκε 529 φορές
-
- Δημοσιεύσεις: 48
- Εγγραφή: Τετ Δεκ 17, 2008 9:42 pm
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
Όχι δεν είναι ταξινομημένα, δεν το λέει πουθενά αυτό, αλλά αν όντως παίζει η λύση σου με μια ταξινόμηση των στοιχείων δεν θα έχεις πρόβλημα, λίγο πιο αργή αλλά λογικά καλύτερη απο Ο(Ν^3)
Re: Με τι πολυπλοκότητα λύσατε το θέμα Β' Φάσης Λυκείου;
simfwnw me ton george, ta arxeia dn eine taxinomimena......georgeha98 έγραψε:Όχι δεν είναι ταξινομημένα, δεν το λέει πουθενά αυτό, αλλά αν όντως παίζει η λύση σου με μια ταξινόμηση των στοιχείων δεν θα έχεις πρόβλημα, λίγο πιο αργή αλλά λογικά καλύτερη απο Ο(Ν^3)
PS:Sorry gia ta greeklish alla grafo pio grigora(msn style xD)