To tylko jedna z 21 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
ALGORYTM Złożoność obliczeniowa 2 Pojęcie algorytmu Algorytm jest ciągiem kroków obliczeniowych prowadzących do przekształcenia danych wejściowych w dane wyjściowe. 3 Każdy algorytm: posiada dane wejściowe produkuje pewien wynik jest precyzyjnie zdefiniowany jest skończony Algorytm jest poprawny, gdy dla każdego zestawu sensownych danych wejściowych zatrzymuje się i daje dobry wynik. 4 Analiza algorytmów Analiza algorytmów to dział informatyki zajmujący się szukaniem najlepszych algorytmów dla zadań komputerowych. 5 Analiza algorytmów pozwala odpowiedzieć na pytania: czy dany problem może być rozwiązany na komputerze w dostępnym czasie i pamięci które ze znanych algorytmów należy zastosować czy istnieje lepszy algorytm od rozważanego jak uzasadnić, że stosując dany algorytm rozwiąże się zamierzone zadanie 6 Dokonując analizy algorytmu zwracamy uwagę na: jego poprawność semantyczną prostotę czas działania ilość zajmowanej pamięci optymalność okoliczności, w jakich należy go używać, a w jakich nie 7 Złożoność obliczeniowa Złożoność obliczeniową algorytmu definiuje się jako ilość zasobów komputerowych, potrzebnych do jego wykonania. Podstawowymi zasobami są: czas działania (złożoność czasowa) ilość zajmowanej pamięci (złożoność pamięciowa) 8 Rozmiar danych Jednym z decydujących parametrów mających wpływ na złożoność obliczeniową jest rozmiar danych . Pojęcie rozmiaru danych: •dla funkcji sortującej - rozmiar tablicy •dla drzewa binarnego - liczba węzłów w drzewie •dla programu obl.silnię - wielkość danej wejściowej •dla wielomianu - stopień wielomianu 9 Złożoność pamięciowa Za jednostkę złożoności pamięciowej przyjmuje się słowo pamięci maszyny. 10 Złożoność czasowa Złożoność czasowa danego algorytmu powinna nie zależeć od komputera, języka programowania czy sposobu zakodowania. W tym celu wyróżnia się w algorytmie charakterystyczne dla niego operacje, nazywane operacjami dominującymi . Za jednostkę złożoności czasowej przyjmuje się wykonanie jednej operacji dominującej. 11 Operacje dominujące Algorytmy sortowania - porównanie dwóch elementów lub przestawienie elementów w ciągu algorytmy przeglądania drzewa binarnego - przejście dowiązania między węzłami w drzewie algorytmy wyznaczania wartości wielomianu - operacje arytmetyczne +, -, *, / 12 Złożoność obliczeniowa algorytmu
... zobacz całą notatkę
Komentarze użytkowników (0)