 |
Coders' city
Nasza pasja to programowanie!
|
| Zobacz poprzedni temat :: Zobacz następny temat |
| Autor |
Wiadomość |
qwe
Gość
|
 Wysłany: Nie Gru 04, 2011 6:34 pm Temat postu: Liczenie złożoności czasowej |
  |
|
Załóżmy, że mamy algorytm przykładowy :
operacje wykonywane są w pętli (warunkiem stopu jest i = ilości elementów w tablicy)
| Kod: |  
 if (x>0)
 x=x+y[i];
 else
 x=y[i];
 a=Max(a,x)
|
No właśnie jak określić złożoność takiego algorytmu(wiem że liniowa)? Co w takim wypadku jest operacją dominującą? |
|
| Powrót do góry |
|
 |
|
|
Kamzor
Dołączył: 17 Paź 2009
Posty: 450
Skąd: Wrocław
|
| Wysłany: Sro Gru 07, 2011 12:23 pm Temat postu: Re: Liczenie złożoności czasowej |
|
|
Złożoność obliczeniowa algorytmu jest funkcją liczby operacji elementarnych od rozmiaru danych. W tym przypadku można założyć że wszystkie operacje mają koszt równy 1, z wyjątkiem wywołania funkcji która ma nieznacznie większą stałą.
| Kod: |
if(x > 0) // 1
x = x + y[i]; // 1
else
x = y[i]; // 1
a = Max(a,x); // 1
|
Skoro pętla wykonuję się n razy to złożoność algorytmu wynosi 3n, czyli O(n). Dokładniejszych analiz raczej rzadko się stosuje ;)
_________________
Free/Libre Open Source Software.
Szkoła jest złą instytucją. |
|
| Powrót do góry |
|
|
|
|
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum
|
Debug: strone wygenerowano w 0.07344 sekund, zapytan = 7
|
Pomoc
Szukaj
Użytkownicy
Grupy
Rejestracja
Profil
Zaloguj się, by sprawdzić wiadomości
