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

Για την πολυπλοκότητα ενός αλγορίθμου χρησιμοποιούμε το συμβολισμό O (O-notation, όπου το O προέρχεται από τη λέξη order και προφέρεται "big-oh"). Ο συμβολισμός O(f(n)) σημαίνει ότι όταν το n μεγαλώνει ο χρόνος εκτέλεσης του αλγορίθμου είναι ανάλογος το πολύ με την f(n). Οι πιο σημαντικές τιμές της f(n) είναι οι εξής:

ΣυμβολισμόςΌνομαΠαράδειγμα
O(1)σταθερή (constant)αναζήτηση σε πίνακα
O(lgn)λογαριθμική (logarithmic)δυαδική αναζήτηση
O(n)γραμμική (linear)σύγκριση συμβολοσειρών
Ο(nlgn)nlgnmergesort
O(n2)τετραγωνική (quadratic)απλές μέθοδοι ταξινόμησης
O(n3)κυβική (cubic)πολλαπλασιασμός πινάκων
O(2n)εκθετική (exponential)μερισμός συνόλου

Για κάθε πρόβλημα αναζητούμε έναν αλγόριθμο με την καλύτερη δυνατή απόδοση.

Παραδείγματα Ασυμπτωτικής Συμπεριφοράς

Ο παρακάτω πίνακας δείχνει το χρόνο που απαιτείται για την εκτέλεση αλγορίθμων συγκεκριμένης πολυπλοκότητας για προβλήματα από 20 έως 1000 στοιχεία. Θεωρούμε ότι κάθε βήμα απαιτεί 1 microsecond (Tarjan 1983).

Complexity-Size20501002005001000
1000n0.02 sec0.05 sec0.1 sec0.2 sec0.5 sec1 sec
1000nlgn0.09 sec0.3 sec0.6 sec1.5 sec4.5 sec10 sec
100n20.04 sec0.25 sec1 sec4 sec25 sec2 min
10n30.02 sec1 sec10 sec1 min21 min2.7 hr
nlgn0.4 sec1.1 hr220 days125 cent5×108 cent 
2n/30.0001 sec0.1 sec2.7 hr3×104 cent  
2n1 sec35 yr3×104 cent   
3n58 min2×109 cent    
n!771 cent9.6×1048 cent    

Ο παρακάτω πίνακας δείχνει το μέγιστο μέγεθος προβλήματος που μπορεί να λυθεί σε συγκεκριμένο χρόνο (Tarjan 1983).

Complexity-Time1 sec102 sec104 sec106 sec108 sec1010 sec
  (1.7 min)(2.7 hr)(12 days)(3 yr)(3 cent)
1000n10310510710910111013
1000nlgn1.4×1027.7×1035.2×1053.9×1073.1×1092.6×1011
100n2102103104105106107
10n3462.1×1021034.6×1032.1×104105
nlgn22365479112156
2n/3597999119139159
2n192633394653
3n121620252933
n!91113141618

Ένας αργός αλγόριθμος δεν επιταχύνεται σημαντικά με τη χρήση καλύτερου υλικού, όπως φαίνεται από τον παρακάτων πίνακα (Aho, Hopcroft and Ullman, 1974, σ. 3):

ΑλγόριθμοςΠολυπλοκότηταΑρχικό μέγεθος προβλήματοςΜέγεθος προβλήματος με χρήση 10 φορές γρηγορότερου υλικού
A1ns110s1
A2nlgns2Περίπου 10s2 για μεγάλα s2
A3n2s33.16s3
A4n3s42.15s4
A52ns5s5 + 3.3

Σύγκριση αλγορίθμων

O παρακάτω αλγόριθμος bubblesort (Cormen et al. 2001, σ. 38) ταξινομεί n στοιχεία A[1],..., A[n] σε χρόνο O(n2):

  
  for i = 1 to length[A]
      for j = length[A] downto i + 1
          if A[j] < A[j - 1]
	      exchange A[j] with A[j-1]
  

Ο παρακάτω αλγόριθμος merge sort (Aho, Hopcroft and Ullman, 1974, σ. 67) ταξινομεί n στοιχεία A[1],..., A[n] σε χρόνο O(nlgn):

  
  procedure mergesort(i, j)
  if i = j
      return A[i]
  else
      m = (i + j - 1) / 2
      return merge(mergesort(i, m), mergesort(m + 1, j))