Αλγοριθμική ερώτηση

[imitheos]

Ο χρόνος εκτέλεσης όντως θα είναι εντελώς διαφορετικός πράγμα που αποδεικνύεται και πολύ εύκολα αν για παράδειγμα σκεφτούμε μία λίστα με 30 στοιχεία και μία με 5. Αν υπάρχει δείκτης prev θα χρειαστεί 30+5=35 περάσματα ενώ αν δεν υπάρχει θα χρειαστεί 2*30+5=65 περάσματα.

 

Ο nik234 όμως ανέφερε το Ο για αυτό είπα ότι 2*ν1+ν2 => ν1 + ν2. Στο μυαλό μου, το O το ερμηνεύω ως "πόσο καλά κλιμακώνεται ο αλγόριθμος" δηλαδή την πολυπλοκότητα όπως είπε ο defacer και όχι την απόλυτη τιμή οπότε μας ενδιαφέρουν πολύ μεγάλα νούμερα προς άπειρο και έτσι το 2*ν1 είναι ίδιο με το ν1.

 

Η wikipedia όμως αναφέρει "In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity" οπότε εκτός από το infinity αφήνει ανοιχτό και το "particular value". Έτσι επειδή δεν έχω ασχοληθεί ιδιαίτερα με το θέμα ανέφερα ότι μπορεί να λέω μπούρδες και να μην ισχύουν αυτά που έγραψα.

 

Επίσης, γνωρίζει κάποιος κάποιον καλύτερο αλγόριθμο σε σχέση με την αρχική ερώτηση του nik234, γιατί έχω την αίσθηση πως υπάρχει αλλά δεν μπορώ να τον θυμηθώ/βρω;

    n1 = N1-1;
    n2 = m = 0;
    while ((n1 >= 0) && (n2 < N2) )
    {
        if ( n1asc[n1] > n2des[n2] )
            mdes[m++] = n1asc[n1--];
        else
            mdes[m++] = n2des[n2++];
    }
    while (n1 >= 0)
	    mdes[m++] = n1asc[n1--];
    while (n2 < N2)
	    mdes[m++] = n2des[n2++];

Η πρώτη μορφή που μου ήρθε χτες στο μυαλό είναι η παραπάνω αλλά είναι πιο αργή από αυτή που έγραψες. Για όσο έχουμε στοιχεία και από τις δύο λίστες τα ελέγχουμε. Όταν μια από τις δύο τελειώσει βγαίνουμε από το βρόχο και μετά απλά κάνουμε append τα στοιχεία που έχουν μείνει (φυσικά μόνο ένα από τα 2 τελευταία while θα τρέξει).

 

Θα μπορούσε δηλαδή κάποιος να επιβεβαιώσει/διαψεύσει ότι δεν χρειάζεται έλεγχος των ορίων των n1 και n2 στον κώδικα που έδωσα με δεδομένο πως οι 2 λίστες είναι σε αύξουσα σειρά η 1η και σε φθίνουσα η 2η;

Όλοι οι έλεγχοι είναι πάντα ευπρόσδεκτοι

n1asc[N1] = {1, 5, 10, 100};    /* ASCendantly ordered */
n2des[N2] = {200, 80, 4};    /* DEScendantly ordered */

Στην παρούσα περίπτωση δεν σου χρειάζεται γιατί τα στοιχεία στους πίνακές σου είναι ανάκατα οπότε δουλεύει τζάμι. Αν όμως τα στοιχεία ήταν

n1asc[N1] = {30, 35, 40, 45};
n2des[N2] = { 10, 5, 2 };

Σε μια περίπτωση όπως αυτή, θα μειώνεται (ή θα αυξάνεται αντίστοιχα) ο μετρητής μόνο του ενός πίνακα με συνέπεια να περάσει το όριο. Εδώ για παράδειγμα το n1 μειώνεται συνεχόμενα και φτάνει να γίνει -1 και μετά συγκρίνεται το -1 με τα n2=0,n2=1,n2=2

[defacer]

Ο nik234 όμως ανέφερε το Ο για αυτό είπα ότι 2*ν1+ν2 => ν1 + ν2. Στο μυαλό μου, το O το ερμηνεύω ως "πόσο καλά κλιμακώνεται ο αλγόριθμος" δηλαδή την πολυπλοκότητα όπως είπε ο defacer και όχι την απόλυτη τιμή οπότε μας ενδιαφέρουν πολύ μεγάλα νούμερα προς άπειρο και έτσι το 2*ν1 είναι ίδιο με το ν1.

 

Αυτό που λες είναι σωστό, αλλά ο λόγος που νομίζω ότι δίνεις δεν είναι σωστός.

 

Με τη μαθηματική έννοια του O το ζητούμενο είναι να βρεις μια συνάρτηση F(n) για την οποία ο χρόνος εκτέλεσης του αλγορίθμου -- έστω T(n) -- είναι πάντα μικρότερος από C * F(n) για κάποια (αυθαίρετα επιλεγμένη) τιμή της σταθεράς C και για οποιοδήποτε n μεγαλύτερο κάποιου (αυθαίρετα επιλεγμένου) n'. Αν βρεις μια τέτοια συνάρτηση, τότε μπορείς να πείς ότι ο αλγόριθμος είναι O(F(n)).

 

Η δυνατότητα της αυθαίρετης επιλογής του C είναι αυτό που κάνει το O(n) να είναι το ίδιο πράγμα με το O(2n), μιας και είναι το ίδιο πράγμα να πεις ότι η F(n) = 2n και C = 1 και το να πεις ότι η F(n) = n σκέτο και C = 2.

 

Η δυνατότητα της αυθαίρετης επιλογής του n' είναι αυτό που μας επιτρέπει να απαλείψουμε τους μικρότερους όρους του πολυωνύμου υπολοιπόμενους όρους της συνάρτησης, μιας και π.χ. εφόσον για n > 1 ισχύει πάντα n < n² τότε μπορούμε να πούμε πως επιλέγω n' = 2, άρα για n > n' ισχύει n² + n < 2n², επομένως εφόσον θέλουμε απλά ένα άνω όριο μπορούμε να πούμε ότι το 2n² είναι εξίσου καλό όσο το n² + n. Αλλά τότε από την προηγούμενη παράγραφο προκύπτει πως το O(2n²) εκφράζει το ίδιο με Ο(n²), επομένως και το Ο(n² + n) εκφράζει το ίδιο με το Ο(n²).

 

Αυτός λοιπόν είναι ο λόγος (προκύπτει δηλαδή από το μαθηματικό ορισμό του Ο), και όχι ότι "εφόσον το n είναι άπειρο, 2n και n είναι το ίδιο πράγμα".

 

Η wikipedia όμως αναφέρει "In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity" οπότε εκτός από το infinity αφήνει ανοιχτό και το "particular value". Έτσι επειδή δεν έχω ασχοληθεί ιδιαίτερα με το θέμα ανέφερα ότι μπορεί να λέω μπούρδες και να μην ισχύουν αυτά που έγραψα.

 

Και τώρα καταλαβαίνεις γιατί αφήνει και ανοιχτό το "particular value". Για πολλές συναρτήσεις, όπως τα απλά πολυώνυμα που χρησιμοποίησα παραπάνω, δε χρειάζεται να πας μέχρι το άπειρο για να βρεις το n' που θα σου επιτρέψει να παίξεις μπάλα.

 

Βεβαίως και το link του migf1 παραπάνω λέει το ίδιο πράγμα (χρησιμοποιεί μάλιστα και σχεδόν τις ίδες μεταβλητές), δηλαδή:

 

 

Formal definition:

• A function T(N) is O(F(N)) if for some constant c and for all values of N greater than some value n₀: T(N) <= c * F(N)

 

 

Απλά μερικές φορές όπως λένε math is hard, let's go shopping.

[migf1]

Ο χρόνος εκτέλεσης όντως θα είναι εντελώς διαφορετικός πράγμα που αποδεικνύεται και πολύ εύκολα αν για παράδειγμα σκεφτούμε μία λίστα με 30 στοιχεία και μία με 5. Αν υπάρχει δείκτης prev θα χρειαστεί 30+5=35 περάσματα ενώ αν δεν υπάρχει θα χρειαστεί 2*30+5=65 περάσματα.

 

Ο nik234 όμως ανέφερε το Ο για αυτό είπα ότι 2*ν1+ν2 => ν1 + ν2. Στο μυαλό μου, το O το ερμηνεύω ως "πόσο καλά κλιμακώνεται ο αλγόριθμος" δηλαδή την πολυπλοκότητα όπως είπε ο defacer και όχι την απόλυτη τιμή οπότε μας ενδιαφέρουν πολύ μεγάλα νούμερα προς άπειρο και έτσι το 2*ν1 είναι ίδιο με το ν1.

 

Δεν είναι μόνο στο δικό σου μυαλό έτσι, αυτός είναι ο ορισμός της πολυπλοκότητας Ο(). Ο nik234 όμως δεν προσδιόρισε τι ακριβώς προσπαθεί να πετύχει π.χ. πολυπλοκότητα της τάξης O(n1+n2)... έγραψε: χρόνο O(n1+n2) οπότε άφησε ανοιχτό το ενδεχόμενο εκτός από την γενική πολυπλοκότητα να επιζητάει όντως και χρόνο ως περαιτέρω εξειδίκευση (keep reading για να καταλάβεις τι εννοώ).

 

Αν το ζητούμενο της ερώτησής του σταματάει στη γενικότερη έννοια της κλιμάκωσης που αντιπροσωπεύει το O() τότε προφανώς και σταματάμε στο O(n1+n2), αν και τυπικά (ή ως καλύτερο hint αν προτιμάς) θα ήταν πιο ακριβές να το εξέφραζε ως O(n) όπου n = n1 + n2.

 

Από όσα γνωρίζω κι έχω κιόλας εξασκήσει προφανώς όχι μόνο μόνος μου αλλά και σε συνεργασία με συναδέλφους, όταν παρουσιάζουμε το μέγεθος αναλυμένο μέσα στο τελικό O() τότε συνήθως (κατά κανόνα, κοινός τόπος, κλπ) εννοούμε πως πέρα από την γενική πολυπλοκότητα μας ενδιαφέρει και η περαιτέρω εξειδίκευσή της σε πραγματικές συνθήκες σε ότι αφορά πιο εξειδικευμένα το efficiency (και δη στις συνθήκες του τρέχοντος project μας).

 

Επομένως, όταν εκφράζεις αναλυμένο το μέγεθος μέσα στο O() ουσιαστικά πιάνεις "με ένα σμπάρο 2 τρυγόνια", αφού ουσιαστικά καλύπτεις και τις 2 περιπτώσεις: και την γενικότερη ασυμπτωτική (με dropped τα constants και τα lower terms, επειδή το συγκεκριμένο  αποτελεί στοιχειώδη γνώση για οποιονδήποτε έχει ασχοληθεί έστω και ξόφαλτσα με πολυπλοκότητες) και την ειδικότερη του efficiency η οποία ουσιαστικά περιγράφει τη διαφορά επίδοσης ανάμεσα σε 2 αλγόριθμους ίδιας πολυπλοκότητας και είναι χρήσιμη όταν το μέγεθος (ή τα μεγέθη) είναι οριοθετημένο (προφανώς ως προς το resource στο οποίο αναφέρεται εξαρχής ή έκφραση του O() ).

 

Είναι δηλαδή κι εδώ ακριβώς η ίδια περίπτωση με το O(n/2) που λέγαμε τότε (ευτυχώς εδώ δεν έχουμε -ακόμη τουλάχιστον- "πανηγύρια" περί #loop-iterations που λέγαμε... μάλλον έλεγα... τότε, επίσης στοιχειώδες για όσους ασχοληθεί έστω και ξόφαλτσα με πολυπλοκότητα).

 

Οπότε, αν όντως ο nik234 ενδιαφέρεται και για τα 2, το αναλυμένο μέγεθος μέσα στο O() του είναι μακράν πιο χρήσιμο από το συνειδητά κουτσουρεμένο ασυμπτωτικό.

 

 

Η wikipedia όμως αναφέρει "In mathematics, big O notation describes the limiting behavior of a function when the argument tends towards a particular value or infinity" οπότε εκτός από το infinity αφήνει ανοιχτό και το "particular value". Έτσι επειδή δεν έχω ασχοληθεί ιδιαίτερα με το θέμα ανέφερα ότι μπορεί να λέω μπούρδες και να μην ισχύουν αυτά που έγραψα.

 

    n1 = N1-1;
    n2 = m = 0;
    while ((n1 >= 0) && (n2 < N2) )
    {
        if ( n1asc[n1] > n2des[n2] )
            mdes[m++] = n1asc[n1--];
        else
            mdes[m++] = n2des[n2++];
    }
    while (n1 >= 0)
	    mdes[m++] = n1asc[n1--];
    while (n2 < N2)
	    mdes[m++] = n2des[n2++];

Η πρώτη μορφή που μου ήρθε χτες στο μυαλό είναι η παραπάνω αλλά είναι πιο αργή από αυτή που έγραψες. Για όσο έχουμε στοιχεία και από τις δύο λίστες τα ελέγχουμε. Όταν μια από τις δύο τελειώσει βγαίνουμε από το βρόχο και μετά απλά κάνουμε append τα στοιχεία που έχουν μείνει (φυσικά μόνο ένα από τα 2 τελευταία while θα τρέξει).

 Όλοι οι έλεγχοι είναι πάντα ευπρόσδεκτοι

n1asc[N1] = {1, 5, 10, 100};    /* ASCendantly ordered */
n2des[N2] = {200, 80, 4};    /* DEScendantly ordered */

Στην παρούσα περίπτωση δεν σου χρειάζεται γιατί τα στοιχεία στους πίνακές σου είναι ανάκατα οπότε δουλεύει τζάμι. Αν όμως τα στοιχεία ήταν

n1asc[N1] = {30, 35, 40, 45};
n2des[N2] = { 10, 5, 2 };

Σε μια περίπτωση όπως αυτή, θα μειώνεται (ή θα αυξάνεται αντίστοιχα) ο μετρητής μόνο του ενός πίνακα με συνέπεια να περάσει το όριο. Εδώ για παράδειγμα το n1 μειώνεται συνεχόμενα και φτάνει να γίνει -1 και μετά συγκρίνεται το -1 με τα n2=0,n2=1,n2=2

 

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

 

Στη γενική περίπτωση το γνωρίζω πως χρειάζεται έξτρα έλεγχος και μέριμνα για appending των περισσευούμενων στοιχείων της όποιας λίστας δε εξαντληθεί πρώτη.

 

Ρώτησα περισσότερο για την ειδική περίπτωση που έθεσε ο nik234, δλδ 1 αύξουσα και μια φθίνουσα και μάλιστα με συγκεκριμένη σειρά ... πρώτη η αύξουσα (ή έτσι το ερμήνευσα εγώ).

 

Οπότε ναι μεν δείχνεις να συμφωνείς πως δεν χρειάζεται έλεγχος, αλλά το τελευταίο σου σχόλιο ουσιαστικά συνεπάγεται πως χρειάζεται. Και νομίζω πως έχεις και δίκιο κιόλας, αλλά επιφυλάσσομαι να το ξανακοιτάξω, γιατί τώρα μάλλον ήρθε η ώρα να πάω να την πέσω

 

Btw, thanks για την απάντηση.

[defacer]

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

 

Επίσης θα ήθελα να πω δημοσίως ότι είναι πραγματικά τραγικό το να περνάνε τόνοι απο λασπολογικές σπόντες εναντίον κάποιου (εντελώς τυχαίο παράδειγμα, εναντίον του εαυτού μου στο παραπάνω post) και κανείς να μην έχει να πει τίποτα γι' αυτό παρά μόνο όταν γίνει μπάχαλο οπότε χαλάει το thread. Το κατακριτέο είναι κατακριτέο μόνο όταν μας ενοχλεί προσωπικά;

 

Anyway, όσο φροντίζει κανείς το σπίτι του τόσο θα τον φροντίσει κι αυτό.

[migf1]

...

Απλά μερικές φορές όπως λένε math is hard, let's go shopping.

 

Wonderful idea, there are tons of black-boxes on sale... how nice for so many people.

[nik324]

 

Τότε νομίζω δεν γίνεται σε O(n1+n2) αλλά σε O(2n1 + n2)... όπου n1 το πλήθος στοιχείων της αύξουσας λίστας η οποία πρέπει να αντιστραφεί πρώτα.

 

Αν είχες και tail τότε θα ήταν O(n1+n2) γιατί θα μπορούσες να ξεκινήσεις την αύξουσα λίστα από το τέλος της...

 

 

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N1        4
#define N2        3
#define M        ( N1 + N2 )

/* --------------------------------------------- */
int main( void )
{
    int n1, n1asc[N1] = {1, 5, 10, 100};    /* ASCendantly ordered */
    int n2, n2des[N2] = {200, 80, 4};    /* DEScendantly ordered */
    int m, mdes[M] = {0};            /* DEScendantly ordered */

    n1 = N1-1;
    n2 = m = 0;
    while ( m < M )
    {
        if ( n1asc[n1] > n2des[n2] ) {
            mdes[m] = n1asc[n1];
            n1--;
        }
        else {
            mdes[m] = n2des[n2];
            n2++;
        }
        printf( "%d ", mdes[m] );
        m++;
    }
    putchar( '\n' );

    system( "pause" );   /* Windows only */
    return 0;
}

Έξοδος:

200 100 80 10 5 4 1
Press any key to continue . . .

Δεν κάνω έλεγχο στα όρια των n1 και n2 για να είναι πιο καθαρός ο κώδικας (χρειάζεται όμως να γίνεται έλεγχος).

 

 

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

Εχω την εντυπωση πως αν αλλαχτουν τα στοιχεια τοτε το αποτελεσμα ειναι εντελος λαθος

πχ

   #define N1        5
   #define N2        4
 
......

   int n1, n1asc[N1] = {1, 5, 10, 100,12};
   int n2, n2des[N2] = {200, 80, 4,8};

[migf1]

@nik234:

 

Στο τσακ με πρόλαβες

 

Προφανώς θα βγει λάθος αφού με αυτά τα στοιχεία δεν είναι ταξινομημένες οι λίστες σου. Η αρχική σου ερώτηση δεν αφορούσε λίστες όπου η 1η είναι ταξινομημένη σε αύξουσα σειρά και η 2η σε φθίνουσα;

[Timonkaipumpa]

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

 

Επίσης θα ήθελα να πω δημοσίως ότι είναι πραγματικά τραγικό το να περνάνε τόνοι απο λασπολογικές σπόντες εναντίον κάποιου (εντελώς τυχαίο παράδειγμα, εναντίον του εαυτού μου στο παραπάνω post) και κανείς να μην έχει να πει τίποτα γι' αυτό παρά μόνο όταν γίνει μπάχαλο οπότε χαλάει το thread. Το κατακριτέο είναι κατακριτέο μόνο όταν μας ενοχλεί προσωπικά;

 

Anyway, όσο φροντίζει κανείς το σπίτι του τόσο θα τον φροντίσει κι αυτό.

 

 

defacer

 

 

Έχεις δίκιο.

 

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

 

Μία φορά προσπάθησα... αλλά εκεί ήσουν (και ο migf1) και θυμάστε (εσείς οι 2) πως κατέληξε. 

 

Anyway... περαστικά σας... δεν μπορώ να πω κάτι άλλο

 

 

[defacer]

Επομένως, όταν εκφράζεις αναλυμένο το μέγεθος μέσα στο O() ουσιαστικά πιάνεις "με ένα σμπάρο 2 τρυγόνια", αφού ουσιαστικά καλύπτεις και τις 2 περιπτώσεις: και την γενικότερη ασυμπτωτική (με dropped τα constants και τα lower terms, επειδή το συγκεκριμένο  αποτελεί στοιχειώδη γνώση για οποιονδήποτε έχει ασχοληθεί έστω και ξόφαλτσα με πολυπλοκότητες) και την ειδικότερη του efficiency η οποία ουσιαστικά περιγράφει τη διαφορά επίδοσης ανάμεσα σε 2 αλγόριθμους ίδιας πολυπλοκότητας και είναι χρήσιμη όταν το μέγεθος (ή τα μεγέθη) είναι οριοθετημένο (προφανώς ως προς το resource στο οποίο αναφέρεται εξαρχής ή έκφραση του O() ).

 

Αυτή η προσέγγιση είναι λάθος, μιας και (αναφερθείτε παραπάνω στον ορισμό του O(n) αν χρειάζεται) στον ορισμό του O(n) συμμετέχει η σταθερά C και το "όριο" n' τα οποία δεν εμφανίζονται όμως όταν γράφουμε O(F(n)).

 

Επομένως βλέποντας κάτι του στυλ O(2n), δεν μπορείς να πεις ότι το efficiency όπως το λέει ο migf1 είναι 2n, γιατί (εκτός του ότι δεν ξέρεις αν έχει απαλειφθεί κάποιος όρος του στυλ logn, αν π.χ. είχαμε F(n) = n + logn) δεν ξέρεις επίσης τον όρο C.

 

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

 

Αν τώρα κάποιος θέλει να πει "να υποθέσεις επιπλέον ότι ο όρος C είναι 1", έχω την εξής αντίρρηση: Γιατί είναι 1 και όχι π.χ. 1.5? Το μέτρησες? Αν ναι, τότε γιατί δίνεις άνω φράγμα του χρόνου εκτέλεσης αντί να μας πεις κατευθείαν ακριβώς πόσος είναι σα συνάρτηση του n? Αν πάλι δεν το μέτρησες, τότε γιατί να υποθέσω πως είναι 1;

 

Ας πούμε λοιπόν ότι το C δεν είναι 1, άρα τι είναι; Άγνωστο. Άρα τι νόημα έχει να πούμε ότι το "efficiency" είναι C * κάτι από τη στιγμή που δεν ξέρουμε το C και, σε αντίθεση με το Ο που είναι άνω φράγμα, το "efficiency" είναι ακριβής τιμή;

 

Δεν έχει κανένα νόημα βέβαια.

 

Επίσης δεν μπορείς να πεις ότι το efficiency είναι τάδε, μιας και αυτό θα μπορούσε να ισχύει μόνο για n > n' αλλά δεν ξέρεις ποιό είναι το n' (στο quote αναφέρεται πως το μέγεθος είναι οριοθετημένο, αλλά τι νόημα έχει αυτό όταν δεν ξέρεις ποιό είναι το όριο?).

 

Όλο αυτό το μπέρδεμα οδηγεί σε παράδοξα, όπως π.χ. ότι ενώ είναι γνωστό πως η quicksort με average O(n logn) είναι καλύτερη από την insertion sort με average O(n²), εν τούτοις η διαφορά στο συντελεστή C μεταξύ τους είναι τόσο μεγάλη ούτως ώστε για "μικρές" τιμές του n, η insertion sort είναι γρηγορότερη -- έχει δηλαδή καλύτερο "efficiency". Γι' αυτό το λόγο σε πολλές περιπτώσεις επιλέγουμε να κάνουμε quicksort αλλά όταν το μέγεθος των partitions γίνει αρκετά μικρό (10-20 χοντρικά) το γυρνάμε στη "χειρότερη"  insertion sort.

 

Το point μου: αν ξέρεις ακριβώς ποιό είναι το runtime ενός αλγορίθμου, πες κατευθείαν "το runtime είναι τόσο". To να πάρεις τη σαφώς ορισμένη έννοια του O και να τη μπασταρδέψεις μεταλλάσσοντάς την σε κάτι που δεν είναι O και δεν είναι ούτε και runtime, είναι ακριβώς αυτό: μπαστάρδεμα.

 

Πόσο μάλλον όταν μιλάμε για αλγορίθμους όπου εκτός από το μέγεθος σημασία έχει και η μορφή της εισόδου (π.χ. και πάλι sort), οπότε όλα αυτά τα περι "προ-υπολογίζω το efficiency" πάνε από το παράθυρο. Αυτός είναι και ο λόγος που δημιουργήθηκε η έννοια του Ο και των άλλων ορισμών πολυπλοκότητας εξαρχής: ισχύουν ανεξαρτήτως του είδους της εισόδου.

[nik324]

@nik234:

 

Στο τσακ με πρόλαβες

 

Προφανώς θα βγει λάθος αφού με αυτά τα στοιχεία δεν είναι ταξινομημένες οι λίστες σου. Η αρχική σου ερώτηση δεν αφορούσε λίστες όπου η 1η είναι ταξινομημένη σε αύξουσα σειρά και η 2η σε φθίνουσα;

Οχ εχεις δικιο σορρυ..απλα ειμαι λιγο ζαλισμενος...

 

Αυτο που θελω να ξερω ειναι αν γινεται να κανουμε αυτη τη διαδικασια σε λιστες που δεν εχουν prev δεικτη...

Θα ηταν καλυτερα να αντιστρεφαμε την μια λιστα και μετα να φτιαχναμε την τριτη καινουργια? Αυτο το θεωρω λαθος γιατι η μια λιστα θα χασει την αρχικη της μορφη

[imitheos]

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

Αν εννοείς το σκεπτικό που έδωσα εγώ για το Ο, μέχρι τότε δεν είχε άλλες απαντήσεις έτσι απάντησα για να πάρει μια ιδέα ο OP τονίζοντας βέβαια ότι δεν γνωρίζω το θέμα και μπορεί να είμαι λάθος. Ασχέτως όμως αν γράφω κάτι με επιφύλαξη ή αν ακόμη είμαι σίγουρος για αυτό που έγραψα, εννοείται πως αν είμαι λάθος πρέπει όποιος γνωρίζει τη σωστή λύση να μην το αφήσει έτσι αλλά να με διορθώσει και ευχαριστώ που το έκανες και με μαθηματική εξήγηση κιόλας. Ούτε προσωπικό είναι ούτε τίποτα. Ίσα ίσα καλό μου κάνεις γιατί το μόνο που με ενοχλεί περισσότερο από το να βλέπω να γράφονται ανακριβή πράγματα είναι να τα έχω γράψει εγώ

 

Αυτο που θελω να ξερω ειναι αν γινεται να κανουμε αυτη τη διαδικασια σε λιστες που δεν εχουν prev δεικτη...

Θα ηταν καλυτερα να αντιστρεφαμε την μια λιστα και μετα να φτιαχναμε την τριτη καινουργια? Αυτο το θεωρω λαθος γιατι η μια λιστα θα χασει την αρχικη της μορφη

Γιατί να χάσει την αρχική της μορφή ? Μπορείς την αντιστροφή να την αποθηκεύσεις σε ένα νέο αντικείμενο όπως πχ μια στοίβα που είχα αναφέρει στο προηγούμενο μήνυμα οπότε οι 2 αρχικές λίστες να μην πειραχθούν καθόλου.

[migf1]

Αυτή η προσέγγιση είναι λάθος, μιας και (αναφερθείτε παραπάνω στον ορισμό του O(n) αν χρειάζεται) στον ορισμό του O(n) συμμετέχει η σταθερά C και το "όριο" n' τα οποία δεν εμφανίζονται όμως όταν γράφουμε O(F(n)).

 

Επομένως βλέποντας κάτι του στυλ O(2n), δεν μπορείς να πεις ότι το efficiency όπως το λέει ο migf1 είναι 2n, γιατί (εκτός του ότι δεν ξέρεις αν έχει απαλειφθεί κάποιος όρος του στυλ logn, αν π.χ. είχαμε F(n) = n + logn) δεν ξέρεις επίσης τον όρο C.

...bla bla bla...

 

Αν έχει καταλάβει κανένας τι σχέση έχει το παραπάνω του defacer (καθώς και όλα τα παρακάτω που γράφει, τα "... bla bla bla ..." δηλαδή) με τη δική μου παράγραφο που έχει κάνει quote και υποτίθεται απαντάει βγάζοντάς την και λάθος, παρακαλώ να μου στείλει π.μ.

 

Η παράθεση στην οποία υποτίθεται απαντάει είναι η εξής (τονίζω επίτηδες το σημείο περί efficiency)

 

Επομένως, όταν εκφράζεις αναλυμένο το μέγεθος μέσα στο O() ουσιαστικά πιάνεις "με ένα σμπάρο 2 τρυγόνια", αφού ουσιαστικά καλύπτεις και τις 2 περιπτώσεις: και την γενικότερη ασυμπτωτική (με dropped τα constants και τα lower terms, επειδή το συγκεκριμένο αποτελεί στοιχειώδη γνώση για οποιονδήποτε έχει ασχοληθεί έστω και ξόφαλτσα με πολυπλοκότητες) και την ειδικότερη του efficiency η οποία ουσιαστικά περιγράφει τη διαφορά επίδοσης ανάμεσα σε 2 αλγόριθμους ίδιας πολυπλοκότητας και είναι χρήσιμη όταν το μέγεθος (ή τα μεγέθη) είναι οριοθετημένο (προφανώς ως προς το resource στο οποίο αναφέρεται εξαρχής ή έκφραση του O() ).

 

Κρίνοντας από αυτά που γράφει λοιπόν, εγώ καταλαβαίνω πως διαβάζει το παραπάνω κοκκινισμένο αλλά καταλαβαίνει κάτι σαν κι αυτό:

"Ένα ημι αναλυμένο μέγεθος μέσα στο Ο() ισούται με τον απόλυτο χρόνο επίδοσης του αλγορίθμου ο οποίος (απόλυτος χρόνος) με τη σειρά του ισούται με ένα αναλυμένο μέγεθος μέσα στο Ο()".

 

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

 

Γράφω τα παραπάνω σε περίπτωση που σας ενδιαφέρει η πολυπλοκότητα και θέλετε να ασχοληθείτε περαιτέρω, ώστε να μην νομίζετε πως εγώ έγραψα οτιδήποτε από αυτά στα οποία υποτίθεται μου απαντάει ο defacer.

 

Σε γενικές γραμμές κρατήστε πως το O() είναι θεωρητικό πράγμα και μάλιστα προσεγγιστικά θεωρητικό, και στην πράξη θα σας χρειαστεί μονάχα αν πρόκειται να ασχοληθείτε με τεράστια data-sets. Ακόμα και τότε όμως, συνήθως δεν θα αρκεστείτε μονάχα στην O() ανάλυση, αλλά θα χρειαστεί να βρείτε και μετά από ποια τιμή έχει νόημα αυτό που σας δείχνει το Ο() καθώς και κάτω από ποια τιμή είναι άχρηστο αυτό που σας δείχνει το Ο().

 

Κρατήστε επίσης πως στην πράξη, ανάλογα και την εξειδίκευσή σας, είναι ουκ ολίγες οι περιπτώσεις που δεν σας ενδιαφέρει να ασχοληθείτε με το τι θα γίνει αν το input σας τείνει στο άπειρο ή αν ξεπεράσει μια πολύ μεγάλη τιμή. Για να είμαι απολύτως ακριβής, αυτές οι περιπτώσεις είναι και οι περισσότερες (δλδ μπορεί να περάσουν ακόμα και χρόνια και να μην χρειαστείτε καν να ασχοληθείτε με O()... και πάντα ανάλογα την εξειδίκευσή σας. Πιθανότατα η simplex method να σας φανει πιο χρήσιμη από το O() για γραμμικές λύσεις.

 

Το Ο() όμως είναι χρήσιμο να το γνωρίζετε, βοηθάει να φιλτράρετε σε 1η φάση αλγόριθμους που λύνουν το ίδιο πρόβλημα.

 

Οχ εχεις δικιο σορρυ..απλα ειμαι λιγο ζαλισμενος...

 

Αυτο που θελω να ξερω ειναι αν γινεται να κανουμε αυτη τη διαδικασια σε λιστες που δεν εχουν prev δεικτη...

Θα ηταν καλυτερα να αντιστρεφαμε την μια λιστα και μετα να φτιαχναμε την τριτη καινουργια? Αυτο το θεωρω λαθος γιατι η μια λιστα θα χασει την αρχικη της μορφη

 

Χωρίς prev δείκτη προφανώς δεν μπορείς να κάνεις αυτή την διαδικασία, για αυτό σου είπα πως θα χρειαστείς 2n1. Όπως σου έγραψε εξαρχής και ο ημίθεος, μπορείς να αντιστρέψεις τη λίστα σου, βάζοντάς την π.χ. πρώτα σε μια στοίβα (άρα σε O(n1)) κατόπιν να την ξανατραβήξεις από την στοίβα, δηλαδή αντεστραμμένη (άρα εκ νεου σε O(n1)).

 

Επίσης δεν μας έχεις διευκρινήσει ακόμα αν σε ενδιαφέρει απλώς η ασυμπτωτική πολυπλοκότητα ή/και οι περαιτέρω επιδόσεις.

 

Αν σε ενδιαφέρει μονάχα η ασυμπτωτική, τότε το O(n1+n2) που ρώτησες αρχικά επιτυγχάνεται με τον τρόπο της στοίβας. Απλώς βεβαίωσε πως δεν έχεις κανένα space περιορισμό, γιατί η λύση με την στοίβα σου προσθέτει και Ο(n1) Space (μνήμη δηλαδή).

[nik324]

Οκ ευχαριστω, θα σκεφτω πως θς το κανω και θα ξανα γραψω αν ειναι..

[defacer]

Αν εννοείς το σκεπτικό που έδωσα εγώ για το Ο, μέχρι τότε δεν είχε άλλες απαντήσεις έτσι απάντησα για να πάρει μια ιδέα ο OP τονίζοντας βέβαια ότι δεν γνωρίζω το θέμα και μπορεί να είμαι λάθος. Ασχέτως όμως αν γράφω κάτι με επιφύλαξη ή αν ακόμη είμαι σίγουρος για αυτό που έγραψα, εννοείται πως αν είμαι λάθος πρέπει όποιος γνωρίζει τη σωστή λύση να μην το αφήσει έτσι αλλά να με διορθώσει και ευχαριστώ που το έκανες και με μαθηματική εξήγηση κιόλας. Ούτε προσωπικό είναι ούτε τίποτα. Ίσα ίσα καλό μου κάνεις γιατί το μόνο που με ενοχλεί περισσότερο από το να βλέπω να γράφονται ανακριβή

πράγματα είναι να τα έχω γράψει εγώ

 

Βασικά εννοούσα αυτό (την εισαγωγή δηλαδή). Όσον αφορά τα υπόλοιπα δε νομίζω πως υπάρχει περίπτωση να παρεξηγηθούμε, είτε εγώ διορθώσω εσένα είτε εσύ εμένα. Όπως έγραψε κάποιος πρόσφατα (δε θυμάμαι ποιός και σε ποιο thread), αν βάζεις τη γνώση πάνω από το ego δεν έχεις τέτοια προβλήματα. 

[nik324]

Και ομως δεν εχω την δυνατοτητα να κανω χρηση καποιας βοηθητικης δομης...

 

Μηπως ειναι πολυ πιο απλο απο οτι φανταζομαι;

Θα μπορουσα ανδρομικα να φτασω στο τελος της μια λιστας και καθως επιστρεφουν οι αναδρομες να εκανα συγκρισεις με την αλλη λιστα?

Μου φαινεται αδυνατον αυτο...