Πολυπλοκοτητα

[Star_Light]

Ρε παιδια να ρωτησω κατι επειδη βλεπω οτι επικρατει καποιου ειδους συγχυση .... πιστευω οτι μια εμφωλιασμενη επαναληψη δεν εγγυαται παντα οτι θα έχουμε τετραγωνική πολυπλοκοτητα... εχω άδικο?

 

Για παράδειγμα ο κώδικας :

 

 

 
for(i=0; i<4; i++)
for(j=0; j<4; j++)
array[i][j] = some_value;
 

 

Για εισοδο 16 στοιχειων σε έναν πινακα array[4][4] υλοποιει 16 εντολές ανάθεσης κάποιας τιμής .... αρα έχει γραμμικη πολυπλοκοτητα επι των στοιχειων εισοδου.

[Stavros_Ribo]

Για εισοδο 16 στοιχειων σε έναν πινακα array[4][4] υλοποιει 16 εντολές ανάθεσης κάποιας τιμής .... αρα έχει γραμμικη πολυπλοκοτητα επι των στοιχειων εισοδου.

 

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

 

for(i=0; i<n; i++)

for(j=0; j<n; j++)

array[i][j] = some_value;

 

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

[Star_Light]

Οταν λεω πολυπλοκοτητα εννοω την χρονικη .... δηλαδη με βαση τα στοιχεια της εισοδου που δεχεται ο αλγοριθμος ποσες πραξεις θα κανει πανω σε αυτα και αρα ποση ωρα θα του παρει να τερματισει τον υπολογισμο που χρειαζεται. Για να γεμισει εναν δισδιάστατο πινακα 4 γραμμών και στηλων θα δεχθει 16 στοιχεια και θα κανει 16 αναθέσεις απο array[0][0] - array[0][3] , array[1][0]-array[1][3] , array[2][0] - array[2][3] ,  array[3][0] - array[3][3]. ( 4 + 4 + 4 + 4) Επομενως σε αυτη την περιπτωση μονο η πολυπλοκοτητα ειναι γραμμική ασχετα αν εχεις ή οχι εμφωλιασμενο loop μεσα.

 

Το n εξαρχης ειναι 16 και μετα 16 θα ειναι δεν καταλαβαινω που η διαφορα.....

 

ετσι οπως το γραφει αυτος εδω δεν σε μπερδευει ?

 

http://datastructuresprogramming.blogspot.gr/2010/02/exercise-for-finding-time-complexity-of.html

 

If we have 2 nested loops,
    for(j=0;j < n;j++)
        for(i=0;i < n;i++)
             {statements;}
then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)

[Stavros_Ribo]

Ναι οκ, η πολυπλοκότητα παντως δεν μετριέται σε seconds

Στο παράδειγμά μου πάντως, το πλήθος πράξεων που θα κάνει θα είναι n^2, ενώ στο δικό σου 16. Η ασυμπτοτική πολυπλοκότητα τώρα, θα είναι Θ(n^2) ως προς n, αλλά νομίζω πως οκ, μπορείς να πεις και γραμμική ως προς το συνολικό πλήθος στοιχείων του πίνακα. Δεν ξέρω αν σε καλύπτει αυτό που λέω, αλλά η πολυπλοκότητα ορίζεται ως προς κάτι. O(n^2)=O("συνολικό πλήθος στοιχείων του πίνακα") στο παράδειγμά μου.

[Star_Light]

Βρε παιδι μου η εντολη της αναθεσης και το εσωτερικο loop θα εκτελεστουν 16 φορες οση και η εισοδος στον αλγοριθμο που θα εχει 16 στοιχεια αρα ειναι γραμμικη. Εγω σου ειπα με βαση την εισοδο ο αριθμος των βηματων που θα κανει μεχρι να γεμισει τον πινακα... για μενα αυτο ειναι η χρονικη πολυπλοκοτητα.... εχω καταλαβει λαθος?

 

Σκεψου επισης ενα παραδειγμα που δεχεται μια λέξη 8 γραμματων και με ενα loop εκτυπωνεις καθε χαρακτηρα της λεξης ξεχωριστα και αυτο γραμμικη πολυπλοκοτητα ειναι γιατι παιρνεις σαν εισοδο 8 χαρακτηρες και το loop δουλευει 8 φορες μεχρι να εκτυπωσει και τους 8 (χωρις τον κενο χαρακτηρα στην C).

 

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

Αν πχ έχεις

 

 

 
arr1d[3] = { 1 , 2 , 3};
 
for(i=0; i<3; i++)
for(j=0; j<3; j++)
if( arr1d[i] > arr1d[j])
do_sth;
 

 

Οποτε για εισοδο πινακα 3 στοιχειων  θα κανεις 9 συγκρισεις ....

 

 

 
arr1d[0] με arr1d[0] εως και arr1d[2]  (3 συγκρισεις)
arr1d[1] με arr1d[0] εως και arr1d[2] (3 συγκρισεις)
<<   [2]  << <<                 << <<         << <<

 

Αρα 3^2 = 9. 9 επεξεργασιες με βαση εισοδο 3 στοιχειων. Eτσι δεν ειναι?

 

Φυσικα και δεν μετριεται σε seconds η πολυπλοκοτητα απο την αποψη οτι δεν ξερεις τι ταχυτητα εχουν οι υπολογιστες σου ... μεταγλωτιστες ... βελτιστοποιησεις κτλπ κτλπ

 

p.s Δεν ξερω αν βαλουμε να κανουμε συγκριση και στον δισδιαστατο αν θα μεταβληθει η πολυπλοκοτητα... οποτε εξαρταται απο τον αλγοριθμο που χρησιμοποιεις.... δεν μπορεις να πεις πχ α εχω εμφωλιασμενο loop εχω τετραγωνικη πολυπλοκοτητα αυτο ειναι πολυ επιφανειακη αντιμετωπιση.

Επεξ/σία 23 Μαρτίου 2013 από Star_Light

[Stavros_Ribo]

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

 

If we have 2 nested loops,
    for(j=0;j < n;j++)
        for(i=0;i < n;i++)
             {statements;}
then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)

 

και γενικώς στη σελίδα που έδειξες η πολυπλοκότητα υπολογίζεται πάντα ως προς το n, άρα σωστά η πολυπλοκότητα είναι O(n^2).

Μέσα στα 2 Loops του παραδείγματος λέει statements, άρα π.χ. θα μπορούσες να έχεις χ=χ+1. Αν η αρχική τιμή του χ ήταν 0, το παράδειγμα είναι σαν να σε ρωτάει τι τιμή θα εχει στο τέλος των loops η μεταβλητή χ.

 

δεν μπορεις να πεις πχ α εχω εμφωλιασμενο loop εχω τετραγωνικη πολυπλοκοτητα αυτο ειναι πολυ επιφανειακη αντιμετωπιση.

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

[Star_Light]

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

 

If we have 2 nested loops,

    for(j=0;j < n;j++)

        for(i=0;i < n;i++)

             {statements;}

then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n²)

 

και γενικώς στη σελίδα που έδειξες η πολυπλοκότητα υπολογίζεται πάντα ως προς το n, άρα σωστά η πολυπλοκότητα είναι O(n^2).

Μέσα στα 2 Loops του παραδείγματος λέει statements, άρα π.χ. θα μπορούσες να έχεις χ=χ+1. Αν η αρχική τιμή του χ ήταν 0, το παράδειγμα είναι σαν να σε ρωτάει τι τιμή θα εχει στο τέλος των loops η μεταβλητή χ.

 

Kαλα εννοειται δεν ειπα εγω οτι τα εχει γραψει λαθος ισα ισα ειναι δυσκολο καποιος να τα εχει γραψει λαθος και να τα δημοσιευσει στο Ιντερνετ μετα γιατι θα τα εχει τεσταρει απο πριν οποτε δεν βιαζομαι ... εγω λεω οτι προσωπικα εμενα αμα δεν δω παραδειγμα με μπερδευει αυτο το σκετο n που έχει... αν δεις πιο πανω έχω κανει EDIT με παραδειγματα..... αν μπορεις κοιταξε το. Δεν μπορεις να λες εχω εμφωλιασμενο loop αρα η πολυπλοκοτητα ειναι n^2 τελος αν δεν δεις τις συνολικες πραξεις που γινονται με βαση τα αρχικα δεδομενα της εισοδου που οκ ειναι τα στοιχεια του πινακα εδω.... Το ιδιο πραγμα λεμε νομιζω και εσυ οταν λες ως προς n αυτο εννοεις ποσες πραξεις γινονται

 

EDIT: Εσυ λες αυτο

 

 

 
#include<stdio.h>

int main(void)

{
    int x=0 , n;
    
    printf("Give n > ");
    scanf("%1d", &n);
    
    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
    x=x+1;   
    
    printf("%d" , x);  // x=16 για εισοδο n=4
    
    return 0;
}

 

Σωστοτατο ειναι αλλα σου λεω πρεπει να έχεις και μια εισοδο

εγω τουλαχιστον για να μην μπερδευομαι !!!!

Επεξ/σία 23 Μαρτίου 2013 από Star_Light

[thanos713]

Μα το n είναι η είσοδός σου, όχι το x, το x προκύπτει από την συνάρτηση, η παράμετρος που δίνεις στην συνάρτηση είναι το n.

 

Αν πχ είχες έναν τέτοιο κώδικα 

for (i=0; i<n; i++)
for (j=0; j<k; j++)

 

τι πολυπλοκότητα θα πεις ότι έχει;

[Star_Light]

Μα το n είναι η είσοδός σου, όχι το x, το x προκύπτει από την συνάρτηση, η παράμετρος που δίνεις στην συνάρτηση είναι το n.

 

Αν πχ είχες έναν τέτοιο κώδικα 

for (i=0; i<n; i++)
for (j=0; j<k; j++)

 

τι πολυπλοκότητα θα πεις ότι έχει;

 

Mα και εγω το n λεω οτι ειναι η παραμετρος...

n*k ειναι αυτο αλλα και παλι δεν μπορεις να εισαι σιγουρος οτι πάντοτε θα ειναι n*k πρεπει να δεις τον αλγοριθμο τι εντολη εχεις απο κατω και τι εισοδο έχεις. Έχω λάθος? Πριν δεν το ειδαμε με το γεμισμα των δισδιάστατων?

[thanos713]

Κάπου σε χάνω. Η πολυπλοκότητα του αλγόριθμου, είναι σε κάθε περίπτωση n*k, ό,τι και να υπάρχει από κάτω, γιατί να αλλάζει σύμφωνα με τα κάτω;

 

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

[Star_Light]

Κάπου σε χάνω. Η πολυπλοκότητα του αλγόριθμου, είναι σε κάθε περίπτωση n*k, ό,τι και να υπάρχει από κάτω, γιατί να αλλάζει σύμφωνα με τα κάτω;

 

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

 

Αυτα που ειχαμε γραψει πριν τα ειδες? Εγω λεω αν το n ειναι ο αριθμος γραμμων και k ο αριθμος στηλων του πινακα σε αυτο το loop που δινεις...

 

Δες και εδω

 

http://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop

 

 

Typically (but not always) one loop nested in another will cause O(n^2)

[thanos713]

Αυτα που ειχαμε γραψει πριν τα ειδες? Εγω λεω αν το n ειναι ο αριθμος γραμμων και k ο αριθμος στηλων του πινακα σε αυτο το loop που δινεις...

 

Δες και εδω

 

http://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop

 

 

Typically (but not always) one loop nested in another will cause O(n^2)

Ναι, τα k και n μπορείς να πεις ότι είναι στήλες και γραμμές πίνακα. Όμως συνεχίζω να διαφωνώ. Δεν μπορείς να είσαι γραμμικός με nested loops, σε καμία περίπτωση, μόνο αν ένα από τα δύο loops έχει σταθερό αριθμό εκτλέσεων μπορείς να είσαι. 

 

Πχ. εδώ 

for (i=0; i<n; i++)
for (j=0; j<4; j++)

 

 

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

[Star_Light]

Ε τι να σου κανω ειμαστε 2 και συμφωνουμε και εισαι ενας και διαφωνείς... περαστικά

 

ΤΕΛΟςΠΑΝΤΩΝ περα απο την πλακιτσα τωρα σε τι διαφωνεις οτι ειναι γραμμικη η πολυπλοκοτητα οταν χρησιμοποιουμε 2 loops για να γεμισουμε εναν δισδιάστατο? Δεχεσαι 100 στοιχεια πες και γεμιζεις σε 100 βηματα τι ειναι αυτο? τετραγωνικο ειναι?

 

Και βασικα δεν ειμαστε μονο 2 ειμαστε και 3 -4 αμα παραθεσω και αλλα links. Εκτος και αν δεν εχω καταλαβει εγω τι γινεται...

[thanos713]

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

 

Πιο συγκεκριμένα, εσύ έχεις 16 νούμερα για να μπουν σε δισδιάστατο πίνακα 4x4, ωραία;

 

#include <stdio.h>

int main()
{
    int pinakas[4][4], i, j;
    for (i=0; i<=16; i++)
    {
        pinakas[i/4][(i%4)-1] = i;
    }
    
    for (i=0; i<4; i++)
    {
        for (j=0; j<4; j++)
        {
            printf("%d\n", pinakas[i][j]);
        }
    }
    
    system("pause");
    return 0;       
}

 

Εκτέλεσε το, καθαρά γραμμικό. Και το δικό σου είναι γραμμικό υπό αυτή την έννοια, αλλά τέτοιες περιπτώσεις είναι λίγες και όλες γίνονται και με ένα loop.

 

EDIT: Ίσως έχει κάποιο bug ο κώδικας γιατί τον έγραψα γρήγορα, αλλά τα νούμερα τα βγάζει σωστά (ίσως και τυχαία), θα τον ξανακοιτάξω αύριο.

[Star_Light]

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

 

Πιο συγκεκριμένα, εσύ έχεις 16 νούμερα για να μπουν σε δισδιάστατο πίνακα 4x4, ωραία;

 

#include <stdio.h>

int main()
{
    int pinakas[4][4], i, j;
    for (i=0; i<=16; i++)
    {
        pinakas[i/4][(i%4)-1] = i;
    }
    
    for (i=0; i<4; i++)
    {
        for (j=0; j<4; j++)
        {
            printf("%d\n", pinakas[i][j]);
        }
    }
    
    system("pause");
    return 0;       
}

 

Εκτέλεσε το, καθαρά γραμμικό. Και το δικό σου είναι γραμμικό υπό αυτή την έννοια, αλλά τέτοιες περιπτώσεις είναι λίγες και όλες γίνονται και με ένα loop.

 

 

Ακριβως. Για καθε ενα στοιχειο που έχουμε γινεται και ενα insertion στον πινακα... επειδη πηγες να με τρελανεις οχι τιποτα αλλο

Εγω γενικα συμφωνω απολυτα με την φραση που σου ποσταρισα πριν οτι τυπικα μπορεις να πεις οτι έχεις τετραγωνικη πολυπλοκοτητα στα εμφωλιασμενα αλλα οχι παντα. Και το οχι παντα φανηκε με το παραδειγμα γεμισματος του δισδιαστατου . Μετα φυσικα δωσαμε και ενα παραδειγμα το οποιο δειχνει ακριβως την τετραγωνικη στα εμφωλιασμενα που λογικα αν το προσαρμοσουμε και σε αυτο που εδωσες και εσυ με n και k μετρητες τοτε δινει Ο(n*k) διαφωνεις?

 

p.s Εγω θεωρω πιο ευαναγνωστο παντως να γεμισω εναν δισδιαστατο με ενα nested loop. Φανταζομαι και αρκετοι αλλοι