Ποιος αλγόριθμος έχει γραμμική πολυπλοκότητα O(n);

Ένας αλγόριθμος με γραμμική πολυπλοκότητα O(n) σημαίνει ότι ο χρόνος εκτέλεσης ή η χρησιμοποιούμενη μνήμη αυξάνονται αναλογικά με το μέγεθος των εισερχόμενων δεδομένων n. Παραδείγματα τέτοιων αλγορίθμων είναι:

1. Αναζήτηση του μέγιστου ή ελάχιστου στοιχείου σε έναν πίνακα: Πρέπει να διασχίσετε όλα τα στοιχεία του πίνακα μία φορά.

   # Αναζήτηση του μέγιστου στοιχείου
   def find_max(arr):
       if not arr:
           return None
       max_val = arr[0]
       for element in arr:
           if element > max_val:
               max_val = element
       return max_val
   

2. Γραμμική αναζήτηση: Αναζήτηση ενός συγκεκριμένου στοιχείου σε μια μη ταξινομημένη λίστα μέσω διαδοχικής διαδρομής.

   // Γραμμική αναζήτηση
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Βρέθηκε το στοιχείο
           }
       }
       return -1; // Δεν βρέθηκε το στοιχείο
   }
   

3. Καταμέτρηση της συχνότητας των στοιχείων σε μια λίστα: Για αυτό, πρέπει να διασχίσετε τη λίστα μία φορά, χρησιμοποιώντας π.χ. έναν πίνακα κατακερματισμού ή λεξικό.

   // Καταμέτρηση συχνότητας
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Απλή αντιγραφή πίνακα: Δημιουργία μιας νέας αντιγραφής του πίνακα διασχίζοντας όλα τα στοιχεία του αρχικού πίνακα.

5. Υπολογισμός του αθροίσματος όλων των στοιχείων σε έναν πίνακα: Απαιτεί μια διαδρομή σε όλα τα στοιχεία.

Σε όλα αυτά τα παραδείγματα, ο αριθμός των λειτουργιών είναι άμεσα ανάλογος με τον αριθμό των στοιχείων στα επεξεργαζόμενα δεδομένα.