Θεωρία αλγορίθμων (O(n2) καιO(n log n))

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

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

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

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από chief » 22 Ιαν 2009 22:12

Σε δύο αλγόριθμους Α Β με χρονική πολυπλοκότητα Ο(n^2) και O(nlogn). Είναι δυνατό σε κάποια δεδομένα ο χρόνος εκτέλεσης του αλγόριθμου A να είναι μικρότερος από τον χρόνο εκτέλεσης του αλγόριθμου B;
Καμία ιδέα; έχω λιώσει στο διάβασμα και δεν βρίσκω καμία απάντηση.

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

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από soteres2002 » 23 Ιαν 2009 01:39

Για μικρά n, είναι δυνατό να ισχύει. Για αυτό, άν ο Α είναι μέτριας απόδοσης αλγόριθμος και ο Β είναι βέλτιστος, μπορεί να παρουσιάζουν περίπου ίδια απόδοση για μικρές εισόδους. Η διαφορά τους όμως στην απόδοση γίνεται εμφανής όταν η είσοδος παίρνει μεγάλες τιμές, που αυτό αφορά τη σχεδίαση των αλγορίθμων. Το Ο-notation αφορά την ασυμπτωτική πολυπλοκότητα, δηλ. όταν αυτό το n τείνει στο άπειρο.

Άβαταρ μέλους
cherouvim
Script Master
Δημοσιεύσεις: 3137
Εγγραφή: 13 Ιούλ 2005 22:56
Τοποθεσία: Athens, Greece
Επικοινωνία:

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από cherouvim » 23 Ιαν 2009 08:19

soteres2002 έγραψε:Το Ο-notation αφορά την ασυμπτωτική πολυπλοκότητα, δηλ. όταν αυτό το n τείνει στο άπειρο.
Ε όχι και στο άπειρο. Όταν n=10.000 σε ένα πολύ βαρύ ή άσχημα προγραμματισμένο αλγόριθμο (πχ O(n^3)) και πρέπει να περιμένω 10 δευτερόλεπτα να ολοκληρώσει ο υπολογιστής τότε το n ούτε για αστείο δεν είναι "κοντά στο άπειρο" σε αυτή τη περίπτωση ;)

http://en.wikipedia.org/wiki/Big_O_notation

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

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από soteres2002 » 23 Ιαν 2009 11:58

Μα μιλάμε από θεωρητική σκοπιά για τους αλγόριθμους, και δεν μας νοιάζει πόσα sec κάνει το pc να ολοκληρώσει την εκτέλεση. Όπως και να 'χει η ασυμπτωτική ανάλυση έτσι τα ορίζει αυτά (συγκεκριμένα το n θέλει να μεγαλώνει συνεχώς), και οι τάξεις πολυπλοκότητας μέσα από τους ορισμούς αυτούς προκύπτει (όπου υπάρχει το άπειρο σαν έννοια). Φυσικά και στην πράξη δεν μιλάμε για άπειρο, παρά μόνο στην θεωρητική ανάλυση αλγ.

Άβαταρ μέλους
cherouvim
Script Master
Δημοσιεύσεις: 3137
Εγγραφή: 13 Ιούλ 2005 22:56
Τοποθεσία: Athens, Greece
Επικοινωνία:

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από cherouvim » 23 Ιαν 2009 13:45

soteres2002 έγραψε:Το Ο-notation αφορά την ασυμπτωτική πολυπλοκότητα, δηλ. όταν αυτό το n τείνει στο άπειρο.
Το O-notation πέρα από θεωρία αφορά και real life projects με inputs 100, 10.000 και 100.000 στοιχείων.

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

Θεωρία αλγορίθμων (O(n2) καιO(n log n))

Δημοσίευση από chief » 23 Ιαν 2009 13:52

Δοκίμασα μερικά παραδείγματα αλλά δεν είδα να διαφοροποιείτε κάτι

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

O(n^2)                   O (n log n)
5^2=25 		     5 log 5=3,49
100^2		      100 log 100=200
100^2		      1000 log 1000=3000
10000^2	              10000 log 10000=500000
Καταρχάς εκτός από τις τιμές θα πρέπει να ισχύσει το ερώτημά μου όταν πρόκειται για διαφορετικές ταξινομήσεις. Ψάχνοντας στο διαδίκτυο βρήκα το παρακάτω παράδειγμα.
The importance of this measure can be seen in trying to decide whether an algorithm is adequate, but may just need a better implementation, or the algorithm will always be too slow on a big enough input. For instance, quicksort, which is O(n log n) on average, running on a small desktop computer can beat bubble sort, which is O(n²), running on a supercomputer if there are a lot of numbers to sort. To sort 1,000,000 numbers, the quicksort takes 20,000,000 steps on average, while the bubble sort takes 1,000,000,000,000 steps!

Απάντηση

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

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

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