Ποια είναι η χρονική πολυπλοκότητα μιας δήλωσης IF σε μια γλώσσα προγραμματισμού;

Η χρονική πολυπλοκότητα μιας δήλωσης `if` είναι γενικά o (1) , αλλά με μερικές σημαντικές προειδοποιήσεις. Εδώ είναι μια κατανομή:

Η ιδέα του πυρήνα:σταθερή ώρα

* Η διακλάδωση είναι γρήγορη: Η κύρια λειτουργία σε μια δήλωση `if` αξιολογεί την κατάσταση και αποφασίζει ποιο κλάδο να εκτελέσει. Αυτή είναι μια πολύ γρήγορη, ντετερμινιστική διαδικασία που περιλαμβάνει μια ενιαία σύγκριση (ή μια σειρά από επιχειρήσεις Boolean που μπορούν να θεωρηθούν οριοθετημένες). Οι σύγχρονοι επεξεργαστές είναι εξαιρετικά βελτιστοποιημένοι για διακλάδωση υπό όρους.

* ανεξάρτητο από το μέγεθος εισόδου: Η απόφαση για την εκτέλεση του μπλοκ `if` if` ή του` eλel` block (ή ούτε αν δεν υπάρχει `else`) δεν εξαρτάται από το μέγεθος των δεδομένων εισόδου που επεξεργάζονται από τον περιβάλλοντα αλγόριθμο. Εξαρτάται μόνο από την ίδια την κατάσταση.

Γιατί O (1) μπορεί να είναι παραπλανητικό (το περιβάλλον έχει σημασία!)

Ενώ η εντολή `if` ίδιοι * είναι o (1), ο κωδικός * μέσα στο μπλοκ 'if` block ή` eλ άλλο μπλοκ μπορεί να έχει οποιαδήποτε χρονική πολυπλοκότητα. Αυτό είναι κρίσιμο. Εξετάστε αυτά τα σενάρια:

1. o (1) if-block:

`` `Python

Εάν x> 5:

y =10 # o (1) Ανάθεση

z =x + y # o (1) Προσθήκη

αλλού:

y =20 # o (1) Ανάθεση

`` `

Σε αυτή την περίπτωση, η δήλωση `if` και ο κώδικας μέσα * και τα δύο * υποκαταστήματα είναι o (1). Η συνολική πολυπλοκότητα αυτού του αποσπάσματος είναι O (1).

2. o (n) if-block:

`` `Python

Εάν ο Len (my_list)> 0:

για το I in Range (len (my_list)):# o (n) loop

εκτύπωση (my_list [i])

αλλού:

εκτύπωση ("Η λίστα είναι κενή") # o (1)

`` `

Εδώ, αν η κατάσταση είναι αληθινή, εκτελέσετε ένα βρόχο που επαναλαμβάνει μέσω του `my_list`, καθιστώντας την πολυπλοκότητα του κλάδου` if` o (n). Εάν η κατάσταση είναι ψευδής, εκτελείτε κωδικό O (1). Η * χειρότερη περίπτωση * Η πολυπλοκότητα αυτού του κώδικα είναι O (n), επειδή η δήλωση `if` μπορεί να οδηγήσει στην εκτέλεση του κώδικα O (n).

3. o (n^2) if-block:

`` `Python

Εάν η κατάσταση:

για το I στην περιοχή (n):

για το J στην περιοχή (n):

# Κάποια λειτουργία O (1)

πέρασμα

αλλού:

# O (1) Λειτουργία

πέρασμα

`` `

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

Συνοπτικά

* Η λογική διακλάδωσης της δήλωσης `if` είναι o (1).

* Η συνολική χρονική πολυπλοκότητα του κώδικα που περιέχει τη δήλωση `if` εξαρτάται εξ ολοκλήρου από την πολυπλοκότητα του κώδικα * μέσα * τα μπλοκ` if` και `ese else. Το μπλοκ με την υψηλότερη πολυπλοκότητα θα κυριαρχήσει.

* Όταν αναλύετε τους αλγόριθμους, πρέπει να εξετάσετε το χειρότερο σενάριο, το οποίο συνήθως περιλαμβάνει το `if` block με την υψηλότερη πολυπλοκότητα που εκτελείται.

Επομένως, ενώ μπορείτε να πείτε ότι η ίδια η δήλωση `if` * παίρνει σταθερό χρόνο, πρέπει πρέπει Αναλύστε τον κώδικα μέσα στα κλαδιά για να προσδιορίσετε την πραγματική χρονική πολυπλοκότητα του μπλοκ κώδικα που περιέχει το «if». Εστίαση στον κυρίαρχο όρο (το μπλοκ κώδικα που θα πάρει το μεγαλύτερο για να εκτελεστεί καθώς το μέγεθος εισόδου μεγαλώνει).