Algorytm – pojęcie, ocena efektywności algorytmu (złożoności obliczeniowej)

Last modified: 20 July 2024

Algorytm to zestaw instrukcji, który określa sekwencję działań prowadzących do rozwiązania problemu. Algorytm jest zbiorem kroków, które muszą być wykonane w określonej kolejności, aby uzyskać pożądany wynik.

Ocena efektywności algorytmu

Efektywność algorytmu to miara złożoności obliczeniowej, czyli ilości zasobów potrzebnych do wykonania algorytmu. Można wyróżnić:

  • Złożoność czasową - ilość czasu potrzebnego do wykonania algorytmu.

  • Złożoność pamięciową - ilość pamięci potrzebnej do wykonania algorytmu.

  • Złożoność obliczeniową - ilość operacji arytmetycznych potrzebnych do wykonania algorytmu.

Notacja dużego O

Notacja dużego O to sposób określania złożoności obliczeniowej algorytmu. Określa ona górne ograniczenie na ilość operacji potrzebnych do wykonania algorytmu.

Przykłady:

  • - stała

  • - logarytmiczna

  • - liniowa

  • - wielomianowa

  • - wykładnicza

  • - silnia