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

[antemar]

Μήπως μπορεί κάποιος να με βοηθήσει στο εξής:

Έχω τις πιο κάτω συναρτήσεις που καλούνται με όρισμα μόνο κάποιο θετικό ακέραιο n>0. Ποια είναι η πολυπλοκότητα ως προς το n για κάθε μια;

f1(n)

1. while n > 1

2. do n  n – 1

 

f2(n)

1. while n > 1

2. do n 

 

f3(n)

1. while n > 1

2. do for i  1 to n

3. do j  1

4. n  n –1

[darth_revan]

Σε ποια γλώσσα είναι γραμμένες? Το λέω γιατί με μπλέκει λίγο ο συμβολισμός. Πάντως αν καθεμία από αυτές είναι ένα while loop, για να βρεις την πολυπλοκότητα χειρότερης περίπτωσης αρκεί απλά να βρεις πόσες φορές το πολύ θα εκτελεστεί το συγκεκριμένο loop...

[antemar]

Είναι σε C.

[tampatas]

Καλά ο παραπάνω κώδικας δεν είναι C, ψευδοκώδικας είναι.

Αν μας πείς τι σιμαίνει το ερωτηματικό, θα βγεί η άκρη.

[darth_revan]

Αν μπορείς, μου εξηγείς για παράδειγμα τι κάνει αυτό:

while n > 1

do n 

Έχω μπερδευτεί κάπως. (Το "?" είναι ο γνωστός "τριαδικός" τελεστής;; )

[panayiotispatra]

F1(n) : O(n)

F2(n) : O(lgn)

F3(n) : O(n2)

[darth_revan]

Μπορεί κάποιος να μου εξηγήσει, τι κάνει αυτός ο κώδικας σε C?? Δεν βγάζω άκρη. Είναι σίγουρα C??

[antemar]

Σας παραθέτω την σωστή μορφή του ψευδοκώδικα:

 

f1(n)

1. while n > 1

2. do n <-- n – 1

 

f2(n)

1. while n > 1

2. do n <-- n/2

 

f3(n)

1. while n > 1

2. do for i <-- 1 to n

3. do j <--1

4. n <-- n –1

[darth_revan]

Σας παραθέτω την σωστή μορφή του ψευδοκώδικα:

 

f1(n)

1. while n > 1

2. do n <-- n – 1

 

f2(n)

1. while n > 1

2. do n <-- n/2

 

f3(n)

1. while n > 1

2. do for i <-- 1 to n

3. do j <--1

4. n <-- n –1

 

Ok. Τώρα συνενοούμαστε. Νομίζω ότι ο panayiotispatra είναι σωστός...

[antemar]

O panayiotispatra έστειλε την εξής απάντηση:

 

F1(n) : O(n)

F2(n) : O(lgn)

F3(n) : O(n2)

 

Μπορεί κάποιος να μου την αιτιολογήσει;