Α' Φάση 22ου ΠΔΠ "Αυτοκίνητα Υδρογόνου"

[stathis]

Ο real.

Πάρτε και από μένα χρόνο της ίδιας λύσης σε pascal, στο test #2:

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

[stathis@osiris]:/home/stathis> time ./hydrogen
0.000u 0.000s 0:00.00 0.0%      0+0k 0+0io 0pf+0w

[pman]

Ευχαριστω για την απάντηση Στάθη.

[kernelpanic]

Εγω τωρα γυρισα Αθηνα (/home sweet /home) αλλα δε βλεπω να το γραφω σημερα, νυσταζωωωω

[pman]

Επιτρέπεται να φτιάξουμε topic που να λέμε την πολυπλοκότητα του προγράμματος μας?

[stathis]

Έχει τόσα πολλά να πούμε που θέλει και topic;

[chris]

Μια χαρά είναι το πρόβλημα. Δίνει την δυνατότητα σε όλους να το λύσουν και να περάσουν, και σε όσους ξέρουν κάτι παραπάνω να κάνουν quick*ΓΚΟΥΧΟΥ*
Εγώ ακόμα δεν άρχισα Θα κάνω μια μπουλμπουλίθρα πρόχειρη τώρα κ μετά βλέπουμε

[pman]

Εμένα η πολυπλοκότητα φτάνει :
2*O(N) + O(N*(N-1))
εσάς?

[thetrojan01]

Το θέμα το είδα στα πολύ πρόχειρα διότι χθες, Κυριακή, έλειπα, και μετά έχω φροντιστήρια... Θα το τυπώσω αυτές τις μέρες.... Όσον αφορά την ταξινόμηση, C++ STL FTW!

[chris]

Εμένα η πολυπλοκότητα φτάνει :
2*O(N) + O(N*(N-1))
εσάς?

Εννοείς Ο(2Ν) + Ο(Ν^2) δηλαδή πάνω κάτω Ν^2

[kernelpanic]

Εφτιαξα τη nlogn βερσιον, και παω για Θ(Ν)

[compileGuy]

Εφτιαξα τη nlogn βερσιον, και παω για Θ(Ν)

Υπάρχει και λύση Θ(Ν) ???

Εγώ μέχρι n log n έχω πάει

[kernelpanic]

Εξαρταται απ'τη τελικη μορφη τιυ προβληματος, μπορει και να μην ισχυει...

Ο(3Ν)best case
Θ(Ν!)worst case

[chris]

Εφτιαξα τη nlogn βερσιον, και παω για Θ(Ν)

Να υποθέσω πως μιλάς για Best Case Performance... Θ(Ν) Ταξινόμηση φυσικά και δεν γίνεται, τουλάχιστον χωρίς κάποιον επαναστατικό αλγόριθμο "Kernelpanic's Algorithm"
Μωρέ ποιός αλγόριθμός έχει nlogn...

Spoiler: show

ΓΙΑΤΙ ΑΝΟΙΓΕΙΣ SPOILER; TI ΠΕΡΙΜΕΝΕΙΣ ΝΑ ΔΕΙΣ;

[kernelpanic]

Τον ειχα αναφερει στο καμπ...

Spoiler: show

Βοηθεια: λεγεται (ωχ! το ξεχασα!)-sort, τι κριμα

[stathis]

Εφτιαξα τη nlogn βερσιον, και παω για Θ(Ν)

Υπάρχει και λύση Θ(Ν) ???

Εγώ μέχρι n log n έχω πάει

Δε παίζει να υπάρχει Θ(Ν) λύση σ' αυτό.
nlogn είναι το κατώτερο.

[compileGuy]

Συνύθως μετράμε τη πολυπλοκότητα του αλγόριθμου με worst case η τουλάχνιστον average case. To !N είναι τρομερά μεγάλο

[kernelpanic]

Ναι αλλα δε νομιζω οι διοργανωτες να ειναι τοσο πολυ κακοι για να το κανουν αυτο,
Βασικα το θεμα δεν εχει αρκετες λεπτομερειες...
Και αν δε μου βγει, δεν πειραζει, εχω τη nlogn για καθε ενδεχομενο

Spoiler: show

Υπολογιζω χοντρικα <4Ν για νορμαλ περιπτωσεις

[pman]

Ναι αλλά στον κώδικα σας υπάρχει σίγουρα μία Ο(2Ν) που δεν μπορείται να αποφύγετε όσο και να θέλεται.

[compileGuy]

Ναι αλλά στον κώδικα σας υπάρχει σίγουρα μία Ο(2Ν) που δεν μπορείται να αποφύγετε όσο και να θέλεται.

Ακρβώς για αυτό δεν έχει νόημα να το λέμε

Λέγε απλά πολυπλοκότητα αλγόριθμου.Μην λες Ο(2Ν)+... που αναγκαστικά όλοι έχουν

[thetrojan01]

αντε αρχίζω την υλοποίηση κι εγώ