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ść 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ść czasowa - zależność pomiędzy liczbą operacji elementarnych wykonywanych w trakcie przebiegu algorytmu a rozmiarem danych wejściowych (podawana jako funkcja rozmiaru tych danych) 

np.

❘ sortowanie bąbelkowe: F( N) = ?, gdzie N jest długością listy

❘ algorytm rozwiązywania problemu wież Hanoi: F( N) = ?, gdzie N jest liczbą krążków 

❘ wyznaczanie minimalnego drzewa rozpinającego: F( N,M) = ?, gdzie N jest liczbą wierzchołków a M - liczbą krawędzi w grafie (sieci połączeń )

Złożoność pamięciowa - to wielkość pamięci niezbędnej do wykonania algorytmu.

Skończoność algorytmów

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

Zapis w języku C++

#include <iostream>

#include <cmath>

using namespace std;

float st, rad;

int main ()

{ 

     st=0.0;

     do

     {

          rad=st*M_PI/180;

          cout << "cos(" <, st << ") = "  << cos(rad)  << endl;

          st+=10.0

     }

     while (cos(rad)!=0.0);

     return 0;

}

Poprawność algorytmów

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

Całkowicie poprawny - dla wszystkich danych wejściowych spełniających warunki początkowe wyprowadzi wyniki spełniające warunki końcowe i obliczenia zostaną zakończone. 

Częściowo poprawny - dla obliczeń, które się skończą wyniki są poprawne względem warunków początkowych i końcowych.

Algorytm powinien być dobrze określony i uniwersalny!

Sortowanie w języku C++ (pozycyjne)

Sortowanie to 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).

2. PRZYKŁAD SORTOWANIA POZYCYJNEGO.

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 w języku C++ (bąbelkowe)

Sortowanie to 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 w języku C++ (przez wybór)

Sortowanie to 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;

}