Efektywność algorytmów

Złożoność obliczeniowa algorytmu jest pojęciem teoretycznym.W praktyce bardziej interesuje nas efektywność algorytmu, która bierze pod uwagę praktyczne zastosowanie algorytmu w programie.

Złożoność obliczeniowa algorytmów

Jest to jeden z najważniejszych parametrów charakteryzujących algorytm. Decyduje on o efektywności całego programu.Podstawowymi zasobami systemowymi uwzględnianymi w analizie algorytmów są czas działania oraz obszar zajmowanej pamięci.

• Przez czasową złożoność obliczeniową rozumiemy ilość czasu niezbędnego do rozwiązania problemu w zależności od liczby danych wejściowych.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
• Złożoność pamięciowa określa z kolei liczbę komórek pamięci, która będzie zajęta przez dane i wyniki pośrednie tworzone w trakcie pracy algorytmu.

• 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

Skończoność algorytmów

Algorytm jest skończony, jeżeli gwarantuje wyznaczenie wyniku w skończonej liczbie kroków.

Algorytm, który nie jest skończony, nie może zostać uznany za poprawny, bowiem nigdy nie spowoduje wyznaczenia poprawnego wyniku.

Algorytm powinien być skończony dla wszystkich danych wejściowych , to znaczy, że żadna ich kombinacja, dopuszczona przez specyfikacje problemu nie powinna powodować sytuacji , w której algorytm się nie kończy.

Poprawność algorytmów

Algorytm jest poprawny, jeżeli rozwiązuje problem zgodnie ze specyfikacją problemu (zadania).

• Algorytm jest całkowicie poprawny , jeśli dla wszystkich danych wejściowych spełniających warunki początkowe wyprowadzi wyniki spełniające warunki końcowe i obliczenia zostaną zakończone
• Algorytm jest częściowo poprawny , jeśli dla obliczeń, które się skończą , ich wyniki są poprawne względem względem warunków początkowych i końcowych.W tym przypadku nie jest konieczne wykazanie , że obliczenia kończą się dla wszystkich poprawnych danych.

Sortowanie pozycyjne w C++

Sortowanie-porządkowanie informacji według określonego kryterium.

1. SORTOWANIE POZYCYJNE.

   W algorytmie sortowania słów według porządku                           alfabetycznego metodą pozycyjną porównywane

   są litery umieszczone na tych samych pozycjach, 

   począwszy od ostatniej litery w najdłuższym słowie 

   (słowach).

Przykład:

Posortować algorytmem sortowania pozycyjnego zbiór liczb:
{ 547 398 247 153 121 792 421 }

Liczby posortujemy wg kolejnych od końca cyfr:

start	??x	?x?	x??	koniec
547 398 247 153 121 792 421	121 421 792 153 547 247 398	121 421 547 247 153 792 398	121 153 247 398 421 547 792	121 153 247 398 421 547 792

Po posortowaniu ostatniej cyfry liczby tworzą ciąg posortowany.

Sortowanie bąbelkowe C++

Sortowanie-porządkowanie informacji według określonego kryterium.

1. SORTOWANIE BĄBELKOWE.

Polega na porównywaniu parami kolejnych liczb i przestawianiu ich jeśli   występują w niewłaściwej kolejności.Sortowanie bąbelkowe jest bardzo 

łatwe - sprawdzamy czy następny element tablicy jest większy od aktualnego,   jeżeli tak, to zamieniamy te elementy miejscami. Aby skrócić czas wykonywania całego algorytmu kosztem dłuższego czasu przejścia przez jedną   pętlę, można utworzyć flagę przechowującą zmiany. Flaga jest zerowana na wejściu w pętli, w przpadku zmiany jest ona podnoszona. Po wykonaniu pętli sprawdzamy czy zaszła zmiana, jeżeli nie to kończymy sortowanie.


    2. PROGRAM REALIZUJĄCY ALGORYTM SORTOWANIA 
       BĄBELKOWGO.

#include<iostream>

using namespace std;

int main()
{
    cout << "*****Bubble sort*****" << endl;
    int a[50],n,i,j,temp;
    cout<<"Wpisz ilosc liczb ";
    cin>>n;
    cout<<"Wypisz elementy: " << endl;
    for(i=0;i<n;++i)
        cin>>a[i];

    for(i=1;i<n;++i)
    {
        for(j=0;j<(n-i);++j)
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
    }

    cout<<"Posortowane liczby:";
    for(i=0;i<n;++i)
        cout<<" "<<a[i];

    return 0;

}

Sortowanie przez wybór w C++

SORTOWANIE-porządkowanie informacji według określonego kryterium.

1. SORTOWANIE PRZEZ WYBÓR.   

Polega na wyszukaniu w ciągu liczby największej (lub najmniejszej- w zależności od przyjętego porządku), ustawieniu jej na początku ciągu, a następnie powtarzaniu tych czynności z pominięciem już uporządkowanych elementów.


      2.PROGRAM REALIZUJĄCY ALGORYTM SORTOWANIA                     PRZEZ WYBÓR: 

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    cout << "*****Select sort*****\n" ;
   int array[100], n, c, d, position, swap;

   printf("Wpisz liczbe elementow\n");
   scanf("%d", &n);

   printf("Wypisz te elementy\n", n);

   for ( c = 0 ; c < n ; c++ )
      scanf("%d", &array[c]);

   for ( c = 0 ; c < ( n - 1 ) ; c++ )
   {
      position = c;

      for ( d = c + 1 ; d < n ; d++ )
      {
         if ( array[position] > array[d] )
            position = d;
      }
      if ( position != c )
      {
         swap = array[c];
         array[c] = array[position];
         array[position] = swap;
      }
   }

   printf("Posegregowane liczby:\n");

   for ( c = 0 ; c < n ; c++ )
      printf("%d\n", array[c]);

   return 0;

}