Złożoność algorytmów

Algorithm Complexity

What is Algorithm Complexity?

• Measures the amount of computational resources (time and space) required by an algorithm to solve a problem
• Typically expressed as a function of the input size (usually denoted as 'n')

Big O Notation

• Used to classify algorithms based on their complexity
• Provides an upper bound on the number of steps an algorithm takes
• Examples:
  • O(1) - constant time complexity (e.g., accessing an array by index)
  • O(log n) - logarithmic time complexity (e.g., binary search)
  • O(n) - linear time complexity (e.g., finding an element in an array)
  • O(n log n) - linearithmic time complexity (e.g., merge sort)
  • O(n^2) - quadratic time complexity (e.g., bubble sort)
  • O(2^n) - exponential time complexity (e.g., recursive algorithms with no optimization)
  • O(n!) - factorial time complexity (e.g., brute-force algorithms for the traveling salesman problem)

Time Complexity vs. Space Complexity

• Time complexity: measures the number of computational steps required
• Space complexity: measures the amount of memory required
• Both are important to consider when evaluating an algorithm's efficiency

Analyzing Algorithm Complexity

• Worst-case analysis: considers the maximum time or space required for an algorithm
• Average-case analysis: considers the average time or space required for an algorithm
• Amortized analysis: considers the total time or space required for a sequence of operations

Importance of Algorithm Complexity

• Helps predict the scalability of an algorithm
• Informs the choice of algorithm for a particular problem
• Enables optimization and improvement of algorithms

Złożoność Algorytmów

Czym jest złożoność algorytmu?

• Mierzy się ilość zasobów obliczeniowych (czasu i miejsca) potrzebnych do rozwiązania problemu przez algorytm
• Zazwyczaj wyrażana jako funkcja rozmiaru wejścia (zwykle oznaczanego jako 'n')

Notacja dużego O

• Używana do klasyfikacji algorytmów ze względu na ich złożoność
• Dostarcza górnego ograniczenia na liczbę kroków algorytmu
• Przykłady:
  • O(1) - stała złożoność czasowa (przykładowo, dostęp do tablicy przez indeks)
  • O(log n) - złożoność czasowa logarytmiczna (przykładowo, wyszukiwanie binarne)
  • O(n) - liniowa złożoność czasowa (przykładowo, wyszukiwanie elementu w tablicy)
  • O(n log n) - liniowo-logarytmiczna złożoność czasowa (przykładowo, sortowanie przez scalenie)
  • O(n^2) - kwadratowa złożoność czasowa (przykładowo, sortowanie bąbelkowe)
  • O(2^n) - eksponencjalna złożoność czasowa (przykładowo, algorytmy rekursywne bez optymalizacji)
  • O(n!) -silna złożoność czasowa (przykładowo, algorytmy siłowe dla problemu komiwojażera)

Złożoność czasowa vs. Złożoność przestrzenna

• Złożoność czasowa: mierzy liczbę kroków obliczeniowych
• Złożoność przestrzenna: mierzy ilość wymaganej pamięci
• Obie są ważne przy ocenie efektywności algorytmu

Analiza złożoności algorytmu

• Analiza najgorszego przypadku: bierze pod uwagę maksymalny czas lub miejsce wymagane przez algorytm
• Analiza przypadku średniego: bierze pod uwagę średni czas lub miejsce wymagane przez algorytm
• Analiza amortyzowana: bierze pod uwagę całkowity czas lub miejsce wymagane przez sekwencję operacji

Znaczenie złożoności algorytmu

• Pomaga przewidywać skalowalność algorytmu
• Informuje wybór algorytmu dla danego problemu
• Umożliwia optymalizację i poprawę algorytmów