Złożoność obliczeniowa algorytmów

Złożoność obliczeniowa algorytmów to miara efektywności algorytmu pod względem czasu wykonania (złożoność czasowa) oraz zużycia pamięci (złożoność pamięciowa). Poniżej omówiono kilka podstawowych pojęć oraz przykłady analizy złożoności algorytmów.

Złożoność czasowa algorytmów

Złożoność czasowa algorytmu odnosi się do ilości czasu, jaki algorytm potrzebuje do zakończenia obliczeń w zależności od wielkości danych wejściowych. Często używa się notacji Big-O do wyrażenia złożoności czasowej, która skupia się na najgorszym przypadku.

Złożoność pamięciowa algorytmów

Złożoność pamięciowa algorytmu odnosi się do ilości pamięci potrzebnej do przechowywania danych podczas wykonywania algorytmu. Również używa się notacji Big-O.

Notacja Big-O (notacja dużego O)

Notacja Big-O opisuje górną granicę złożoności algorytmu, co oznacza, że daje ona przybliżenie maksymalnego czasu lub pamięci potrzebnej przez algorytm.

Przykłady notacji Big-O

O(1) - Stała złożoność, czas wykonania nie zależy od wielkości danych wejściowych.
O(log⁡ n) - Logarytmiczna złożoność, czas wykonania rośnie logarytmicznie wraz z wielkością danych wejściowych.
O(n) - Liniowa złożoność, czas wykonania rośnie liniowo wraz z wielkością danych wejściowych.
O(n log ⁡n) - Liniowo-logarytmiczna złożoność, typowa dla algorytmów sortujących jak Quick Sort czy Merge Sort.
O(n2) - Kwadratowa złożoność, czas wykonania rośnie kwadratowo wraz z wielkością danych wejściowych, np. algorytmy sortujące bąbelkowo.
O(2n) - Eksponencjalna złożoność, czas wykonania rośnie eksponencjalnie, typowe dla algorytmów rozwiązujących problemy NP-trudne.

Analiza złożoności wybranych algorytmów

Sito Eratostenesa

Algorytm znajdowanie liczb pierwszych do n

  • Złożoność czasowa - O(n log ⁡n)
  • Złożoność pamięciowa - O(n)
def eratosthenes_sieve(limit):
 sieve = [True] * (limit + 1)
 for num in range(2, int(limit**0.5) + 1):
 if sieve[num]:
 for multiple in range(num*num, limit + 1, num):
 sieve[multiple] = False
 return [num for num in range(2, limit + 1) if sieve[num]]

Sortowanie przez wstawianie

Sortowanie listy

  • Złożoność czasowa - O(n2)
  • Złożoność pamięciowa - O(1)
def insertion_sort(arr):
 for i in range(1, len(arr)):
 key = arr[i]
 j = i - 1
 while j >= 0 and key < arr[j]:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key
 return arr

Quick sort

Sortowanie listy

  • Złożoność czasowa:
    • średnia - O(n log ⁡n)
    • najgorszy przypadek - O(n2)
  • Złożoność pamięciowa - O(log⁡ n)
def quick_sort(arr):
 if len(arr) <= 1:
 return arr
 pivot = arr[len(arr) // 2]
 left = [x for x in arr if x < pivot]
 middle = [x for x in arr if x == pivot]
 right = [x for x in arr if x > pivot]
 return quick_sort(left) + middle + quick_sort(right)

Wyszukiwanie binarne

Wyszukiwanie elementu w posortowanej liście

  • Złożoność czasowa - O(log⁡ n)
  • Złożoność pamięciowa - O(1)
def binary_search(arr, target):
 left, right = 0, len(arr) - 1
 while left <= right:
 mid = (left + right) // 2
 if arr[mid] == target:
 return mid
 elif arr[mid] < target:
 left = mid + 1
 else:
 right = mid - 1
 return -1

Złożoność obliczeniowa algorytmów jest kluczowym elementem w ocenie ich efektywności. Notacja Big-O jest powszechnie stosowana do opisania tej złożoności. Rozumienie złożoności czasowej i pamięciowej pomaga w wyborze odpowiedniego algorytmu do konkretnego problemu, co jest szczególnie ważne w przypadku dużych zbiorów danych.

Komentarze