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

[migf1]

Προφανέστατα εγώ είμαι αυτός που έγραψε τις μπούρδες! Σαφώς και ΔΕΝ θα είναι ταξινομημένο το αποτέλεσμα μετά από την βλακεία που έγραψα και πολύ σωστά διόρθωσε ο ημίθεος.

 

Sorry about that.

[nik324]

Εχω μονο δεικτες head και οχι tail...

[migf1]

Τότε νομίζω δεν γίνεται σε 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 αλγόριθμος, αλλά δεν μου έρχεται στο μυαλό κάτι αυτή τη στιγμή.

[nik324]

Οκ σε ευχαριστω...Θα το μελετησω περισσοτερο και θα δω τι θα κανω

[migf1]

Ok, εμένα μου δημιουργήθηκε άλλη απορία όμως: όντως χρειάζεται έλεγχος για τα όρια των n1 και n2 στον κώδικα που έδωσα; Τελικά νομίζω πως δεν χρειάζεται (αλλά έχω κολλήσει τώρα και δεν είμαι σίγουρος).

[defacer]

Η σειρά του επόμενου να εξηγήσει ότι O(n1 + n2) είναι το ίδιο πράγμα με Ο(2n1 + n2) -- εγώ και ο ημίθεος αποτύχαμε.

[migf1]

Η σειρά του επόμενου να εξηγήσει ότι O(n1 + n2) είναι το ίδιο πράγμα με Ο(2n1 + n2) -- εγώ και ο ημίθεος αποτύχαμε.

 

http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#constants

 

 

 

Δεν ξέρω για τον ημίθεο, αλλά εσύ εκτός από ότι προφανέστατα έχεις αποτύχει (από αυτά που λες και γράφεις) είσαι κι ανεπίδεκτος μάθησης: http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#constants

 

 

[defacer]

Κοίτα, έχω κι άλλες δουλειές να κάνω από το να ασχολούμαι μαζί σου. Η ίδια σελίδα που κάνεις link λέει

 

Recall that when we use big-O notation, we drop constants and low-order terms. This is because when the problem size gets sufficiently large, those terms don't matter.

 

However, this means that two algorithms can have the same big-O time complexity, even though one is always faster than the other. For example, suppose algorithm 1 requires N² time, and algorithm 2 requires 10 * N² + N time. For both algorithms, the time is O(N²), but algorithm 1 will always be faster than algorithm 2. In this case, the constants and low-order terms do matter in terms of which algorithm is actually faster.

 

Αν δεν καταλαβαίνεις πως "χρόνος εκτέλεσης κατ΄ απόλυτη τιμή" (στον οποία παίζουν ρόλο οι σταθεροί συντελεστές) και "αλγοριθμική πολυπλοκότητα" (αυτό που περιγράφουμε τα το big-oh και τα υπόλοιπα σχετικά notations, στο οποίο δεν παίζουν ρόλο οι συντελεστές) είναι τελείως διαφορετικά πράγματα τα οποία αποτιμούνται με διαφορετικό τρόπο, that's OK with me. Απλά μη παίρνεις κι άλλο κόσμο στο λαιμό σου.

[migf1]

Κοίτα, έχω κι άλλες δουλειές να κάνω από το να ασχολούμαι μαζί σου.

 

Τότε να μην ασχολείσαι και πολύ περισσότερο να μην με προκαλείς.

 

Η ίδια σελίδα που κάνεις link λέει

 

 

Αν δεν καταλαβαίνεις πως "χρόνος εκτέλεσης κατ΄ απόλυτη τιμή" (στον οποία παίζουν ρόλο οι σταθεροί συντελεστές) και "αλγοριθμική πολυπλοκότητα" (αυτό που περιγράφουμε τα το big-oh και τα υπόλοιπα σχετικά notations, στο οποίο δεν παίζουν ρόλο οι συντελεστές) είναι τελείως διαφορετικά πράγματα τα οποία αποτιμούνται με διαφορετικό τρόπο, that's OK with me. Απλά μη παίρνεις κι άλλο κόσμο στο λαιμό σου.

 

Το αν και τι καταλαβαίνω εγώ και πολύ περισσότερο το τι γνωρίζω, έχω εμπεδώσει και θεωρητικά και πρακτικά το έχω ήδη περιγράψει συνοπτικά ( http://www.insomnia.gr/topic/480501-πολυπλοκοτητα/page-3#entry52253923 ).

 

Το τι δεν καταλαβαίνεις εσύ (ειδικά όταν διαβάζεις δημοσιεύσεις λιγάκι πιο advanced από την Wikipedia) και πολύ περισσότερο το τι δεν ξέρεις δεν με αφορά, παρά μόνο όταν με προκαλείς.

 

Για το ποιος από τους 2 μας παίρνει κόσμο στο λαιμό του, άσε να το κρίνει ο κόσμος (ιδιαίτερα όταν τύχει να τα αντιμετωπίσει στη πράξη).

[defacer]

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

[migf1]

 

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

 

http://www.insomnia.gr/topic/467655-αλγοριθμική-ερώτηση/page-4#entry52264491

 

Οπότε, αυτά αλλού.

 

 

[ChRis6]

Εμένα μου φαίνεται οτι O(n1+n2) και O(2n1+n2) έχουν την ίδια γραμμική πολυπλοκότητα .

Μπορεί να κάνω και λάθος βέβαια,γιατί πάντα οι ασύμπτωτες συναρτήσεις με νευρίαζαν

[migf1]

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

[pmav99]

έλεος... Σταματήστε ρε να φαγώνεστε με τα ίδια και τα ίδια. Μπαίνουμε να διαβάσουμε ένα thread προγραμματισμού όχι ξεκατινιάσματα. Μην κάνετε έτσι http://xkcd.com/386/

[migf1]

έλεος...

 

Συμφωνώ κι επαυξάνω!

 

Οπότε μπορούμε να επιστρέψουμε στην κανονική ροή του νήματος πριν την εκ νέου εμφάνιση του defacer με τα περί αποτυχιών, επόμενου, μη χρόνου του να ασχολείται (αλλά να ασχολείται) κλπ;

 

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

 

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