ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU

Złożoność czasową wyrażamy albo w jednostkach czasu, albo w liczbie operacji dominujących, które należy wykonać dla n danych, aby otrzymać rozwiązanie problemu. Operacja dominująca jest operacją, której wykonanie bezpośrednio wpływa na czas wykonania całego algorytmu. Podawanie złożoności czasowej w jednostkach czasu jest niewygodne, ponieważ wynik zależy od szybkości komputera, na którym dokonano pomiarów - trudno takie wyniki odnieść do innych komputerów, szczególnie wyposażonych w inne procesory, gdzie czas wykonania podobnych operacji może znacznie się różnić. Dlatego częściej złożoność czasową wyrażamy w liczbie operacji dominujących, gdyż każdy komputer, bez względu na swoje własności, operacje te musi wykonać. Dzięki temu wynik uniezależniamy od faktycznej szybkości komputerów

Ponieważ często zużycie zasobów w algorytmie uzależnione jest od postaci przetwarzanych danych, zarówno złożoność czasowa jak i pamięciowa może występować w trzech odmianach:

• T_O(n) - optymistycznej (ang. optimistic)
• T_A(n) - średniej (ang. average)
• T_W(n) - pesymistycznej (ang. worst)

Aby poglądowo wyjaśnić powyższe terminy, rozważmy prosty algorytm wyszukiwania robaczywego jabłka w koszu n jabłek. Algorytm jest bardzo prosty:

Dopóki w koszu są jabłka, wyjmij jedno jabłko z kosza, obejrzyj je, jeśli jest robaczywe, to zakończ. Inaczej odłóż je na bok i wróć do początku.

Rozważmy, ile operacji dominujących (ocena jabłka) wykona ten algorytm dla n jabłek.

1. Zakładamy przypadek optymistyczny - robaczywe jabłko napotkamy za pierwszym razem. Zatem:
   T_o(n) = 1 - złożoność optymistyczna
2. Zakładamy przypadek najgorszy - w koszu brak jabłek robaczywych lub robaczywe jabłko będzie wyjęte z kosza jako ostatnie:
   T_w(n) = n - złożoność pesymistyczna
3. W przypadku typowym robaczywe jabłko znajdziemy po przeglądnięciu połowy jabłek w koszu - tzn. raz będzie ono wyciągnięte wcześniej, raz później, a średnio w ⁿ/₂ teście:
   T_A(n) = ⁿ/₂ - złożoność średnia, oczekiwana

Zatem podsumowując:

Złożoność optymistyczna określa zużycie zasobów dla najkorzystniejszego zestawu danych.

Złożoność średnia określa zużycie zasobów dla typowych (tzw. losowych) danych.

Złożoność pesymistyczna określa zużycie zasobów dla najbardziej niekorzystnego zestawu danych.

Sortowanie

SORTOWANIE KUBEŁKOWE

Sortowanie kubełkowe jest algorytmem przeznaczonym dla pewnej specyficznej grupy danych. Jest podobnym algorytmem do sortowania przez zliczanie.  Algorytm jest wydajny w sytuacji, gdy dane rozmieszczone równomiernie. Nazwa wzięła się stąd, że dane wrzucamy do kubełków, które są już z definicji posortowane. 

Zalety

• złożoność obliczeniowa jest rzędu {tex}O(n){/tex}
• jest bardzo szybkim algorytmem dla pewnej grupy danych

Wady

• dane powinny być równomiernie rozłożone
• algorytm musi być dostosowany do danego typu danych
• w niektórych sytuacjach trudny w implementacji#include<iostream>

  using namespace std;
   
  void sortowanie_kubelkowe(int tab[], int n)
  {
    //szukanie minimum i maksimum
    int Min = tab[0], Max = tab[0];
    for(int i=1;i<n;i++)
    {
      if(Min > tab[i]) Min = tab[i];
      if(Max < tab[i]) Max = tab[i];
    }
    if(Max - Min > 100000000)
    {
      cout<<"Ten algorytm sobie nie poradzi\n";
      return;
    }
    //tworzenie pomocniczej tablicy
    int *pom = new int [Max - Min + 1];
    //zerowanie tablicy pomocniczej
    for(int i=0;i<Max - Min + 1;i++) pom[i] = 0;
    //zliczanie wartosci
    for(int i=0;i<n;i++) ++pom[tab[i]-Min];
    //zapisywanie posortowanego zbioru do pierwotnej tablicy
    int k=0;
    for(int i=0;i<Max-Min+1;i++)while(pom[i]--)tab[k++]=i + Min;
   
    delete [] pom;
  }
   
  int main()
  {
    int n, *tab;
    cin>>n;
    tab = new int [n+1];
    //wczytanie zbioru
    for(int i=0;i<n;i++) cin>>tab[i];
    //-------------------------------
    sortowanie_kubelkowe(tab, n);
    //-------------------------------
    //wypisanie zbioru
    for(int i=0;i<n;i++) cout<<tab[i]<<" ";
    delete [] tab;
    return 0;
  }