pdp forum

Πείτε μας με τι πολυπλοκότητα το λύσατε, ή ακόμη κι αν δεν το λύσατε ακόμη.
Μπορείτε να αλλάξετε την ψήφο σας, πχ. σε περίπτωση που βρείτε πιο γρήγορο αλγόριθμο.

O(n^2) worst-case

εγώ ρε γαμώτο έχω κολήσει με αυτην τη βλακεία.... χ)

αν μπορει καποιος να help εμενά ας μου στειλει πρωσοπικο μυνημα....


ελπιζω να μην παραβιαζω τους κανόνες..

ιδού και οι καμπύλες πολυπλοκότητας
μπλε->Ο(Ν!)
πράσινο-> Ο(2^Ν)
πορτοκαλί-> Ο(Ν^3)
και (αν υφίσταται)
ροζ-> Ο(Ν^2)
στον άξονα των x είναι ο αριθμός των πόλεων και στον y η πολυπλοκότητα

σχόλια:
1)κατά τη γνώμη μου Ο(Ν^2) δεν μπορεί να υπάρξει, φαίνεται κ από τη διαφορά π χει από όλες τις υπόλοιπες καμπύλες...
2)όποιος έχει βρει πολυπλοκότητα Ο(Ν!) να κάτσει να ψάξει για μια από τις άλλες 2
[vlakia]
3)οι πολυπλοκότητες Ο(2^Ν) και Ο(Ν^3) δεν έχουν τόοσο τεράστια διαφορά πια κ μάλιστα μέχρι τις 10 περίπου πόλεις η Ο(2^Ν) είναι γρηγορότερη[/vlakia]

Δε τίθεται θέμα σύγκρισης 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^Ν είναι πιο εύκολη στην υλοποίηση απο την Ν!.

Τα είπε όλα ο Νίκος, δεν έχω να προσθέσω τίποτα.

thelastnicholas έγραψε:Δε τίθεται θέμα σύγκρισης 2^Ν με Ν^3 σε καμία περίπτωση... Καταρχήν η 2^Ν είναι εκθετική και Ν^3 πολυωνυμική... Μόνο αυτό είναι αρκετό για να συμπεραίνουμε ότι ειναι ΠΟΛΥ ΠΟΛΥ πιο αργή η 2^Ν. Το λάθος που κάνεις είναι οτι εξετάζεις ένα ΥΠΕΡΒΟΛΙΚΑ μικρό εύρος τιμών... Τι συμπέρασμα μπορούμε να βγάλουμε για τη συμπεριφορά της συνάρτησης ότι η μέγιστη τιμή που απεικονίζεται είναι 2800 και ο υπολογιστής εκτελεί 1000000000 πράξεις το δευτερόλεπτο??

Μια καλή 2^Ν δεν μπορεί να τα καταφέρει εντός 5 δευτερολέπτων για Ν>23 . Για Ν=40 θα χρειαζόταν περίπου 3 ώρες (χωρις άλλες πράξεις). Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.

Αντίθετα η Ν^3 για Ν=200 χρειάζεται 0.08 δευτερόλεπτα...

οκ, με πεισες, απλά τραγικό λάθος μου
έχεις απολυτο δίκιο

thelastnicholas έγραψε: Εκεί που δεν υπάρχει ουσιαστική διαφορά για νούμερα μικρότερο του 200 είναι μεταξύ της Ν^2 και της Ν^3. Δε μπορώ να καταλάβω πως μπορεί να αποτελέσει επιχείρημα κατά της ύπαρξης της το ότι Ν^2 είναι πολύ γρήγορη.... Με την ίδια λογική δεν θα έπρεπε να υπάρχει κανέναν αλγόριθμος shortest path αφού είναι πολύ πιο γρήγορος απο τον bruteforce Ν!.

οκ, δεν είναι το βασικό επιχείρημα, αλλά μαθηματικά δεν μπορώ εγώ να καταλαβω (καλά, ουτ αυτό ειν επιχείρημα βασικά) πως θα γινόταν ένα πρόγραμμα σε ν^2, δηλαδή μιλάμε για 2 αντικείμενα π μπορούν να πάρουν ν διαφορετικές τιμές το καθένα; δεν μπορώ να σκευτώ πως θα μοιάζει ο αλγόριθμος...

thelastnicholas έγραψε: Μπορεί στα νούμερα η 2^Ν να φαίνεται πιο γρήγορη απο την Ν^3 αλλά δεν είναι λόγω της χρήσης στοίβας για την υλοποίησης της 2^Ν.
Γενικώς πάντως έχω την εντύπωση οτι η 2^Ν είναι πιο εύκολη στην υλοποίηση απο την Ν!.

όχι ρε συ η ν! βγαίνει με μερικά φορ, η άλλη 2^ν είναι πιο περίπλοκη στην υλοποίηση

Ορίστε το σωστό plot, χωρίς όμως την N!, γιατί με αυτήν αυξάνεται τόσο πολύ, που κάνει τα άλλα να μην φαίνονται.

Παιδιά εγώ το έλυσα με πολυπλοκότητα Ο(Ν)
Ας μου πει κάποιος αν ξέρει πόσο είναι το πλήθος των σημείων στο 3ο αρχείο (κρυφό),
γιατί και στα 3 testcases τελειώνω με χρόνο 0.000 sec.

άμα έχεις Ο(Ν) πολυπλοκότητα τι σε νοιάζει το μέγεθος των αρχείων?? Αν και τέσταρε το πρόγραμμά σου με το hellenico, γιατί εδώ υπάρχουν αμφιβολίες για λύση με πολυπλοκότητα Ο(Ν^2) πόσο μάλλον για Ο(Ν) !

Πες μου λίγο, τι είναι αυτό το hellenico?
Κοίτα τι γίνεται, αυτοί έχουν ένα site για δοκιμές άμα είδες, που ό,τι και να βάλεις (π.χ. 50 σημεία)
το βγάζει σχεδόν αμέσως. Ε, τέτοια ταχύτητα έχει και το δικό μου. Ό,τι έβαζα εκεί (στο site)
το δοκίμαζα και στο πρόγραμμά μου και μου έβγαζε την ίδια λύση σχεδόν αμέσως.

Δοκίμασε να χρησιμοποιήσεις αυτόν http://www.pdpforum.eu.org/forum/viewto ... 1003#p1003 ή αυτόν http://www.pdpforum.eu.org/forum/viewto ... 1030#p1030 τον testcase maker. Αν έστω σε ένα testcase σου βγάλει λάθος, η λύση σου είναι λάθος. Κάνε γρήγορα γιατι οι υποβολές τελειώνουν το βράδυ.

Ενδιαφέρον...
Τι αποτέλεσμα βγάζεις στο αρχειο που έχω επισυνάψει?

!!Διορθωση αρχειου!!

μήπως ξέρει κανείς η λύση Ο(2^ν) πόσο χρόνο κάνει στα 200 λιμάνια? Ναι hambos αυτό το site εννοούσα για να τεστάρεις το πρόγραμμά σου. Αν τα έχεις καταφέρει μπράβο.

ρε, έλεος, αυτό το αρχείο που έβαλες δεν τα έχει ταξινομημένα, περίμενε να τα ταξινομήσω και
θα σου πω

Τα αρχεία που θα δίνονται στο διαγωνισμό δεν θα είναι όλα ταξινομημένα.

τα testcases είναι όλα ταξινομημένα. δεν είναι? νομίζω το λέει

Το έχουμ πει. Για την 2^Ν

Οταν δε το Ν γίνεται 200 χρειάζετα 509556711142500721569622682756583778070206428 χρόνια για να ολοκληρωθει.

Δεν αναφέρεται κάπου οτι τα αρχεία ειναι ταξινομημένα. Το ξανα-επισυναψα ταξινομημένα όμως.

Όχι δεν είναι ταξινομημένα, δεν το λέει πουθενά αυτό, αλλά αν όντως παίζει η λύση σου με μια ταξινόμηση των στοιχείων δεν θα έχεις πρόβλημα, λίγο πιο αργή αλλά λογικά καλύτερη απο Ο(Ν^3)

georgeha98 έγραψε:Όχι δεν είναι ταξινομημένα, δεν το λέει πουθενά αυτό, αλλά αν όντως παίζει η λύση σου με μια ταξινόμηση των στοιχείων δεν θα έχεις πρόβλημα, λίγο πιο αργή αλλά λογικά καλύτερη απο Ο(Ν^3)

simfwnw me ton george, ta arxeia dn eine taxinomimena......

PS:Sorry gia ta greeklish alla grafo pio grigora(msn style xD)