algorytm jest procedurą krok po kroku, która definiuje zestaw instrukcji być wykonane w określonej kolejności, aby uzyskać żądane wyjście. Algorytmy są na ogół tworzone niezależnie od języków bazowych, tzn. algorytm może być zaimplementowany w więcej niż jednym języku programowania.,
z punktu widzenia struktury danych Poniżej przedstawiono kilka ważnych kategorii algorytmów −
-
Search − algorytm do wyszukiwania pozycji w strukturze danych.
-
Sort-algorytm sortowania elementów w określonej kolejności.
-
Insert-algorytm wstawiania elementu do struktury danych.
-
Update-algorytm do aktualizacji istniejącej pozycji w strukturze danych.
-
Delete-algorytm usuwania istniejącej pozycji ze struktury danych.
charakterystyka algorytmu
nie wszystkie procedury można nazwać algorytmem., Algorytm powinien mieć następujące cechy −
-
jednoznaczny-algorytm powinien być jasny i jednoznaczny. Każdy z jego etapów (lub faz), a ich wejścia/wyjścia powinny być jasne i muszą prowadzić tylko do jednego znaczenia.
-
Input-algorytm powinien mieć 0 lub więcej dobrze zdefiniowanych wejść.
-
Output-algorytm powinien mieć 1 lub więcej dobrze zdefiniowanych wyjść i powinien dopasować żądane wyjście.
-
skończoność-algorytmy muszą kończyć się po skończonej liczbie kroków.,
-
wykonalność − powinna być wykonalna z dostępnych zasobów.
-
niezależny-algorytm powinien mieć wskazówki krok po kroku, które powinny być niezależne od dowolnego kodu programowania.
Jak napisać algorytm?
nie ma dobrze zdefiniowanych standardów pisania algorytmów. Jest to raczej zależne od problemów i zasobów. Algorytmy nigdy nie są pisane do obsługi określonego kodu programowania.
ponieważ wiemy, że wszystkie języki programowania dzielą podstawowe konstrukcje kodu, takie jak pętle (do, for, while), sterowanie przepływem (if-else), itp., Te wspólne konstrukcje mogą być użyte do napisania algorytmu.
algorytmy piszemy krok po kroku, ale nie zawsze tak jest. Pisanie algorytmów jest procesem i jest wykonywane po dobrze zdefiniowanej domenie problemu. Oznacza to, że powinniśmy znać dziedzinę problemu, dla której projektujemy rozwiązanie.
przykład
spróbujmy nauczyć się pisania algorytmów za pomocą przykładu.
Problem − Zaprojektuj algorytm dodawania dwóch liczb i wyświetlania wyniku.
Step 1 − STARTStep 2 − declare three integers a, b & cStep 3 − define values of a & bStep 4 − add values of a & bStep 5 − store output of step 4 to cStep 6 − print cStep 7 − STOP
algorytmy mówią programistom jak kodować program., Alternatywnie, algorytm może być zapisany jako −
Step 1 − START ADDStep 2 − get values of a & bStep 3 − c ← a + bStep 4 − display cStep 5 − STOP
w projektowaniu i analizie algorytmów, Zwykle druga metoda jest używana do opisu algorytmu. Ułatwia analitykowi analizę algorytmu ignorując wszystkie niepożądane definicje. Może obserwować, jakie operacje są używane i jak przebiega proces.
zapisywanie liczb kroków jest opcjonalne.
projektujemy algorytm, aby uzyskać rozwiązanie danego problemu. Problem można rozwiązać na więcej niż jeden sposób.,
dlatego dla danego problemu można wyprowadzić wiele algorytmów rozwiązania. Kolejnym krokiem jest analiza zaproponowanych algorytmów rozwiązania i wdrożenie najlepszego odpowiedniego rozwiązania.
Analiza algorytmu
wydajność algorytmu może być analizowana na dwóch różnych etapach, przed wdrożeniem i po wdrożeniu. Są one następujące −
-
Analiza a Priori-jest to teoretyczna analiza algorytmu., Efektywność algorytmu mierzy się przyjmując, że wszystkie inne czynniki, na przykład prędkość procesora, są stałe i nie mają wpływu na implementację.
-
a Posterior Analysis − jest to empiryczna analiza algorytmu. Wybrany algorytm jest zaimplementowany przy użyciu języka programowania. Jest on następnie wykonywany na docelowej maszynie komputerowej. W tej analizie gromadzone są rzeczywiste statystyki, takie jak czas pracy i wymagana przestrzeń.
poznamy analizę algorytmu a priori., Analiza algorytmów zajmuje się wykonywaniem lub czasem wykonywania różnych operacji. Czas pracy operacji można zdefiniować jako liczbę instrukcji komputerowych wykonanych na jedną operację.
złożoność algorytmu
Załóżmy, że X jest algorytmem, a n jest wielkością danych wejściowych, czas i przestrzeń używane przez algorytm X są dwoma głównymi czynnikami, które decydują o wydajności X.
-
Współczynnik czasu − czas mierzony jest przez zliczanie liczby kluczowych operacji, takich jak porównania w algorytmie sortowania.,
-
Współczynnik przestrzeni − przestrzeń jest mierzona przez zliczanie maksymalnej przestrzeni pamięci wymaganej przez algorytm.
złożoność algorytmu f (n) podaje czas działania i/lub przestrzeń dyskową wymaganą przez algorytm w kategoriach n jako rozmiar danych wejściowych.
złożoność przestrzeni
złożoność przestrzeni algorytmu reprezentuje ilość miejsca w pamięci wymaganą przez algorytm w jego cyklu życia., Przestrzeń wymagana przez algorytm jest równa sumie następujących dwóch składników-
-
stała część, która jest przestrzenią wymaganą do przechowywania pewnych danych i zmiennych, które są niezależne od wielkości problemu. Na przykład, proste zmienne i stałe używane, rozmiar programu, itp.
-
część zmiennej jest przestrzenią wymaganą przez zmienne, której rozmiar zależy od wielkości problemu. Na przykład dynamiczna alokacja pamięci, rekurencja przestrzeni stosu, itp.,
złożoność przestrzeni S(P) dowolnego algorytmu p jest S(P) = C + SP(i), gdzie C jest stałą częścią, A S(I) jest zmienną częścią algorytmu, która zależy od właściwości instancji I. Poniżej znajduje się prosty przykład, który próbuje wyjaśnić to pojęcie −
tutaj mamy trzy zmienne A, B i C oraz jedną stałą. Stąd S (P) = 1 + 3. Teraz przestrzeń zależy od typów danych podanych zmiennych i typów stałych i zostanie odpowiednio pomnożona.,
złożoność czasowa
złożoność czasowa algorytmu reprezentuje czas wymagany przez algorytm do uruchomienia do zakończenia. Wymagania czasowe można zdefiniować jako funkcję numeryczną T(n), gdzie T (n) można zmierzyć jako liczbę kroków, pod warunkiem, że każdy krok zużywa stały czas.
na przykład dodanie dwóch N-bitowych liczb całkowitych wykonuje n kroków. W związku z tym całkowity czas obliczeniowy wynosi T (n) = c ∗ n, gdzie c to czas potrzebny na dodanie dwóch bitów. Tutaj obserwujemy, że T(n) rośnie liniowo wraz ze wzrostem wielkości wejściowej.,