Πώς να αξιολογήσετε τη δυσκολία ενός αλγορίθμου ή να…

Η αξιολόγηση της πολυπλοκότητας ενός αλγορίθμου γίνεται μέσω αναλύσεων ασυμπτωτικής, που επιτρέπουν την περιγραφή της αποδοτικότητας του αλγορίθμου ανάλογα με το μέγεθος των εισερχόμενων δεδομένων ($n$). Τα βασικά βήματα:

Ορισμός βασικών λειτουργιών: Επιλέγονται οι λειτουργίες των οποίων ο χρόνος εκτέλεσης εξαρτάται σημαντικά από το $n$ (π.χ., συγκρίσεις, αναθέσεις, αριθμητικές λειτουργίες).
Υπολογισμός αριθμού λειτουργιών: Υπολογίζεται ο αριθμός των βασικών λειτουργιών ανάλογα με το $n$. Μπορεί να είναι μια ακριβής φόρμουλα ή μια εκτίμηση.
Ορισμός ασυμπτωτικής κλάσης: Χρησιμοποιούνται οι σημειώσεις Μεγάλου Ο ($O$), Omega ($\Omega$) και Theta ($\Theta$) για την περιγραφή της ανώτερης, κατώτερης και ακριβούς ασυμπτωτικής συμπεριφοράς αντίστοιχα.

$O(f(n))$: Ο αλγόριθμος εκτελείται σε χρόνο που δεν υπερβαίνει μια σταθερά πολλαπλασιασμένη με το $f(n)$ για μεγάλα $n$. Χρησιμοποιείται για την περιγραφή της χειρότερης περίπτωσης.
$\Omega(f(n))$: Ο αλγόριθμος εκτελείται σε χρόνο που είναι τουλάχιστον μια σταθερά πολλαπλασιασμένη με το $f(n)$ για μεγάλα $n$. Χρησιμοποιείται για την περιγραφή της καλύτερης περίπτωσης.
$\Theta(f(n))$: Ο αλγόριθμος εκτελείται σε χρόνο που είναι ανάλογος με το $f(n)$ για μεγάλα $n$. Χρησιμοποιείται για την μέση περίπτωση ή όταν η καλύτερη και η χειρότερη περίπτωση έχουν την ίδια ασυμπτωτική τάξη.

Η πιο συχνά χρησιμοποιούμενη Μεγάλο $O$ περιγράφει το ανώτατο όριο του χρόνου εκτέλεσης, που είναι σημαντικό για την κατανόηση της κλιμάκωσης του αλγορίθμου στη χειρότερη περίπτωση.

Παραμέληση σταθερών και μικρότερων όρων: Κατά τον ορισμό της ασυμπτωτικής, αγνοούνται οι σταθεροί πολλαπλασιαστές και οι όροι χαμηλότερης τάξης, καθώς για μεγάλα $n$ κυριαρχεί η λειτουργία με τον μεγαλύτερο εκθέτη. Για παράδειγμα, για $3n^2 + 5n + 10$, η ασυμπτωτική είναι $O(n^2)$.

Τυπικές ασυμπτωτικές κλάσεις (σε αύξουσα τάξη πολυπλοκότητας):

$O(1)$: Σταθερή πολυπλοκότητα (ο χρόνος εκτέλεσης δεν εξαρτάται από το $n$).
$O(\log n)$: Λογαριθμική πολυπλοκότητα (ο χρόνος αυξάνεται πολύ αργά με το $n$, χαρακτηριστικό για αλγορίθμους δυαδικής αναζήτησης).
$O(n)$: Γραμμική πολυπλοκότητα (ο χρόνος είναι ανάλογος με το $n$, χαρακτηριστικό για απλή διαδοχική αναζήτηση).
$O(n \log n)$: Γραμμικο-λογαριθμική πολυπλοκότητα (χαρακτηριστικό για αποδοτικούς αλγορίθμους ταξινόμησης, όπως Quick Sort ή Merge Sort).
$O(n^2)$: Τετραγωνική πολυπλοκότητα (ο χρόνος αυξάνεται με το τετράγωνο του $n$, χαρακτηριστικό για απλούς αλγορίθμους ταξινόμησης, όπως Bubble Sort).
$O(n^c)$ (για $c > 1$): Πολυωνυμική πολυπλοκότητα.
$O(c^n)$ (για $c > 1$): Εκθετική πολυπλοκότητα (ο χρόνος αυξάνεται πολύ γρήγορα με το $n$, χαρακτηριστικό για εξερεύνηση όλων των πιθανών επιλογών).
$O(n!)$: Παραγοντική πολυπλοκότητα (η υψηλότερη τάξη, αυξάνεται εξαιρετικά γρήγορα).

Για τον προσδιορισμό της ασυμπτωτικής των κυκλικών δομών:

Σειριακά μπλοκ κώδικα: Προστίθενται οι πολυπλοκότητες των μπλοκ. $O(A+B) = O(\max(A, B))$.
Ενδογενείς βρόχοι: Πολλαπλασιάζεται ο αριθμός των επαναλήψεων. Ένας βρόχος με $n$ επαναλήψεις, μέσα στον οποίο υπάρχει άλλος με $m$ επαναλήψεις, έχει πολυπλοκότητα $O(n \times m)$. Αν $m=n$, τότε $O(n^2)$.
Βρόχοι με μείωση μεγέθους εισόδου: Για παράδειγμα, η διαίρεση με 2 σε κάθε επανάληψη οδηγεί σε λογαριθμική πολυπλοκότητα ($O(\log n)$).

Παράδειγμα:

Απλή διαδοχή πίνακα:

# Επανυπολογισμός βασικών λειτουργιών (συγκρίσεις, αναθέσεις)
# Κύρια λειτουργία - σύγκριση σε βρόχο
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 ανάθεση (εκτός βρόχου)
    for i in range(1, len(arr)): # Εκτελείται $n-1$ φορές
        # Μέσα στον βρόχο:
        # 1 σύγκριση (if arr[i] > max_val)
        # πιθανώς 1 ανάθεση (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Αν το μέγεθος του πίνακα είναι $n = \texttt{len(arr)}$, ο βρόχος εκτελείται $n-1$ φορές. Σε κάθε επανάληψη, εκτελείται σταθερός αριθμός λειτουργιών. Ο συνολικός αριθμός λειτουργιών είναι ανάλογος με το $n$. Ασυμπτωτική πολυπλοκότητα: $O(n)$.

Παράδειγμα: Ταξινόμηση με εισαγωγή (Insertion Sort)

# Επανυπολογισμός βασικών λειτουργιών
# Βασικές λειτουργίες: συγκρίσεις και αναθέσεις/μετακινήσεις στοιχείων

def insertion_sort(arr):
    # Εξωτερικός βρόχος εκτελείται $n-1$ φορές
    for i in range(1, len(arr)):
        key = arr[i] # 1 ανάθεση
        j = i - 1 # 1 ανάθεση
        # Εσωτερικός βρόχος εκτελείται στη χειρότερη περίπτωση $i$ φορές
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 ανάθεση (μετακίνηση)
            j -= 1 # 1 αφαίρεση και 1 ανάθεση
        arr[j + 1] = key # 1 ανάθεση

Ο εξωτερικός βρόχος εκτελείται $n-1$ φορές. Ο εσωτερικός βρόχος στη χειρότερη περίπτωση (αν ο πίνακας είναι ταξινομημένος ανάποδα) εκτελείται κατά μέσο όρο $i$ φορές (ή μέχρι $i$ φορές). Το συνολικό πλήθος λειτουργιών σε όλες τις επαναλήψεις του εξωτερικού βρόχου: $1 + 2 + ... + (n-1) \approx n^2/2$. Ασυμπτωτική πολυπλοκότητα: $O(n^2)$ στη χειρότερη και μέση περίπτωση, $O(n)$ στην καλύτερη περίπτωση (αν ο πίνακας είναι ήδη ταξινομημένος). Στην εκτίμηση της πολυπλοκότητας, συνήθως λαμβάνεται υπόψη η χειρότερη περίπτωση (Μεγάλο $O$).

Πώς να αξιολογήσετε τη δυσκολία ενός αλγορίθμου ή να προσδιορίσετε την ασυμπτωτική του συμπεριφορά;