--> Archiwum Forum
Loczek [ El Loco Boracho ]
algorytmika - obliczanie złożoności obliczeniowej
Witam,
mam na zaraz do przygotowania na zajęcia prezentacje o złożoności algorytmów równoległych. Tak jak o programowaniu mam troche pojęcie to o obliczaniu złożoności nie mam bladego... I nie mówie tu o algorytmach równoległych, ale o zwykłych, jednoprocesorowych.
Może mi ktoś łopatologicznie powiedzieć jak oblicza się złożoność algorytmu?
np. na przykładu silni:
#include <stdio.h>
#include <stdlib.h>
int silnia(int n)
‹
if (n==0)return 1;
else return n*silnia(n-1);
›
int main(int argc, char *argv[])
‹
printf("%i", silnia(5));
system("PAUSE");
return 0;
›
Z góry dziękuje za pomoc
wysiak [ Legend ]
Choroba, zdarzylo mi sie napisac i obronic prace na temat programowania rownoleglego, i juz 10 prawie lat pracuje w zawodzie, a o 'zlozonosci obliczeniowej algorytmu' nie slyszalem... Wot jak ma sie studiowanie do zycia, i jaka wiedze maja absolwenci, w odniesieniu do praktyki..:)
To taki lekki offtop..:)
zmudix [ palnik ]
O w mordę... strzelam: licz kroki dla różnych n i następnie zobacz, do jakiej klasy by się to nadawało?
Loczek [ El Loco Boracho ]
zmudix: no właśnie zastanawiam się czy trzeba liczyć to ręcznie, krok po kroku, czy jest jakaś inna możliwość...
zmudix [ palnik ]
Zawsze możesz dodać zmienną licznik i ją inkrementować z każdym krokiem algorytmu.
Pozostaje też pytanie, czy chodzi o liczbę kroków, czy może czas wykonania? Wtedy sprawa ma się odrobinę inaczej, ale i prościej, bo przed i po uruchomieniu algorytmu wystarczy dopisać funkcję startującą i zatrzymującą zegar. :)
edit: takie coś znalazłem:
A teraz idę spać, jutro kolos, więc chociaż z dwie godzinki się przekimam. ;)
Loczek [ El Loco Boracho ]
Dzień dobry, dziękuje za odpowiedzi... :)
Może napisze w jakiej formie prowadzący wymago tego ode mnie, żeby było wiadomo o co mi chodzi. Poza częścią teoretyczną mam podać przykład prostego algorytmu jednoprocesorowego i pokazać na jego przykładzie jak się liczy złożoność czasową... :)