Nierozstrzygalnośc i złożonośc algorytmiczna
Implementacja
Komputery przetwarzają przekazywane im informacje z wykorzystaniem pewnych algorytmów. Program jest algorytmem zapisanym w języku zrozumiałym dla maszyny (asemblerze). Każdy kod maszynowy da się przełożyć na zestaw instrukcji dla maszyny Turinga.
Zwykle algorytmy pracują na pewnych danych wejściowych i uzyskują z nich dane wyjściowe. Informacje zapisane w pamięci maszyny traktuje się jako jej stan wewnętrzny. Niektóre algorytmy mają za zadanie wyłącznie przeprowadzanie komputera z jednego stanu wewnętrznego do innego.
Każdy algorytm komputerowy musi być wyrażony w bardzo rygorystycznie zdefiniowanym języku. Ludzie często komunikując się przesyłają między sobą informację wieloznaczne. Komputery mogą reagować tylko na całkowicie jednoznaczne instrukcje. Jeżeli dany algorytm da się wykonać na maszynie o dostępnej mocy obliczeniowej i pamięci oraz akceptowalnym czasie, to mówi się że jest obliczalny.
Poprawne działanie większości algorytmów implementowanych w komputerach opiera się na kolejnej realizacji pewnego zestawu warunków. Jeżeli, któryś z nich nie zostanie spełniony, to program kończy się komunikatem błędu. Czasami podczas implementacji algorytmu ważny warunek zostanie pominięty Dla przykładu, mamy program dzielący przez siebie dwie liczby. Użytkownik każe mu dzielić przez zero. Aplikacja bez sprawdzenia warunku “dzielnik nierówny zero” zawiesi się w takiej sytuacji.
Błędy w implementacji
Kiedy komputery stały się powszechne, algorytmy zaczęto masowo wykorzystywać do rozwiązywania problemów życia codziennego. Dzisiaj w miliardach maszyn cyfrowych działają niezliczone zastępy umieszczonych w nich programów. Wiele z nich oblicza stan konta w banku, inne kompresują dźwięk podczas rozmowy telefonicznej, a niektóre z nich dbają o sprawność wyświetlania strony Wikipedii. Jednak rewolucja cyfrowa niesie ze sobą niebezpieczeństwo błędnych implementacji algorytmów. Kody źródłowe programów zabezpieczających większość dzisiejszych systemów przed niepowołanym atakiem mogą okazać się pełne błędów. W takiej sytuacji są one narażone na atak cyberterrorystyczny na światową skalę. Ratunkiem jest tutaj stosowanie jawnych implementacji algorytmów, których kod źródłowy jest otwarty dla każdego. W ten sposób zwiększa się szansa na odnalezienie błędów i ich szybką naprawę. Nie mniej ważne jest stałe aktualizowanie najważniejszych programów przez administratorów ważnych sieci komputerowych. Oczywiście może to być broń obusieczna - wystarczy wyobrazić sobie sytuację w której osoba o złych intencjach dostrzega, i wykorzystuje błąd w kodzie źródłowym programu.
Większość nowoczesnych środowisk programistycznych dostarcza tzw. debugery - programy wspomagające wykrywanie błędów w kodzie programu, poprzez np. możliwość dokładnego prześledzenia jego działania z wglądem na wartości zmiennych.
Wciąż rozwijana inżynieria oprogramowania pozwala na tworzenie aplikacji których kod żródłowy ma setki tysięcy lini, przy równoczesnym zachowaniu kontroli nad całością projektu, jednak, choćby ze względu na statystykę, błędy w programach prawdopodobnie zawsze będą towarzyszyć (coraz większym) projektom.
Zadanie algorytmiczne
Każde zagadnienie przetwarzania wiąże się z wykorzystaniem pewnej istniejącej informacji w celu wygenerowania informacji w jakimś sensie użytecznej. Przedmiotem zainteresowania uczynimy nie tyle same wyniki, co sposoby ich otrzymywania, a ściślej — takie sposoby ich otrzymywania, które da się opisać. Opisy zaś mają być na tyle precyzyjne, by dało się je traktować jako instrukcje do pomyślnego i bezmyślnego wykonywania. Niezależnie od celu, w jakim zostaną podjęte próby przetworzenia informacji, na wstępie niezbędne jest określenie
1. zestawu wymaganych danych wejściowych,
2. zestawu oczekiwanych wyników.
Określenie takie będziemy nazywać specyfikacją użytkową zagadnienia przetwarzania. Charakteryzuje ona działanie pożądanego schematu przetwarzania obserwowane z zewnątrz, bez zagłębiania się w szczegóły przekształcania danych.
Z punktu widzenia osoby zainteresowanej otrzymaniem wyników (nazwijmy ją użytkownikiem) postawienienie specyfikacji kończy sprawę. Jeżeli tylko zadanie jest rozwiązywalne, to zawsze istnieje bardzo wiele (tak naprawdę to nieskończenie wiele) sposobów, w jaki dane wynikowe można by otrzymać z danych wejściowych. Żaden z tych sposobów nie interesuje użytkownika, prawdę mówiąc jest mu wszystko jedno, który z nich zostanie zastosowany — dany sposób postępowania można w każdej chwili zastąpić innym sposobem, byle miał on tę samą specyfikację danych.
Postawimy się teraz w roli konstruktorów i krytyków schematu przetwarzania. W odróżnieniu od użytkownika, będą nas interesować szczegóły, w jaki sposób z danych dostarczonych mają powstawać dane wynikowe, i dlaczego zaproponowany sposób jest — lub nie jest — dobry. Celem naszym będzie budowanie takich schematów. Będziemy się też starać wykazać, że w istocie dla każdego możliwego, lecz sensownego zestawu danych wejściowych, generowane przez schemat dane wynikowe są (lub nie są) zgodne z oczekiwaniami użytkownika wyrażonymi w specyfikacji. Żeby ten cel zrealizować, analizowany schemat musimy skonfrontować z narzuconą specyfikacją danych; bez niej wszystko sprowadzi się do doraźnych manipulacji na danych. Oczywiście nic nie stoi na przeszkodzie, byśmy specyfikację tę określili sami — jednak przed przystąpieniem do ostatecznej konstrukcji schematu.
Kilka przykładów specyfikacji użytkowych
Wyznaczanie rozwiązań równania algebraicznego
Rozważmy dla przykładu możliwe sposoby wyznaczania pierwiastków równania kwadratowego ax2 + bx + c = 0. Poszczególne realizacje tego zagadnienia mogą pobierać dane w kolejności a, b, c lub innej; mogą wyznaczać pierwiastki różnymi sposobami (np. za pomocą wyróżnika, z wzorów Viète'a lub metodami przybliżonymi); mogą wyznaczać rozwiązania rzeczywiste lub zespolone; mogą zwracać sensowne wyniki zawsze albo tylko wtedy, kiedy równanie jest „naprawdę” równaniem kwadratowym (tzn. kiedy a ≠ 0); mogą wreszcie udostępniać wyniki w różnej kolejności, w różnej postaci i z różną dokładnością.
Przykłady:
Przykład 1.
Wyznaczanie wszystkich rozwiązań rzeczywistych równania ax2 + bx + c = 0 o współczynnikach rzeczywistych. Współczynniki a, b, c są kolejno odczytywane z wejścia standardowego. Na wyjściu pojawia się liczba znalezionych rozwiązań, a następnie wartości tych rozwiązań. Każda dana wynikowa jest umieszczana w osobnym wierszu pliku wyjściowego. Wartość −1 liczby rozwiązań oznacza, że równanie jest spełnione tożsamościowo. Wyniki są przedstawiane z pełną dostępną precyzją obliczeń.
Przykład 2.
Wyznaczanie wszystkich rozwiązań rzeczywistych równania ax2 + bx + c = 0 o współczynnikach rzeczywistych. Współczynniki a, b, c są kolejno odczytywane z wejścia standardowego. Dana a nie może przyjmować wartości 0; odpowiedzialny za to jest użytkownik. Na wyjściu drukowane są wartości kolejnych znalezionych rozwiązań. Wyniki są przedstawiane w postaci dziesiętnej z dokładnością do 3 miejsc dziesiętnych. W przypadku braku rozwiązań na wyjściu nie pojawia się żaden znak.
Przykład 3.
Wyznaczanie wszystkich rozwiązań rzeczywistych i zespolonych równania ax2 + bx + c = 0 o współczynnikach rzeczywistych. Dopuszcza się, by danymi wejściowymi były wyrażenia algebraiczne reprezentujące współczynniki. Na wyjściu pojawią się algebraiczne reprezentacje znalezionych rozwiązań.
W sensie drugiej spośród wymienionych specyfikacji, zestaw danych wejściowych 0 1 0 jest nieprawidłowy. Mają one także różną wartość użytkową: nie jest wszystko jedno, jakie rozwiązania zostaną znalezione i z jaką dokładnością zostaną podane. Według trzeciej z podanych specyfikacji wyniki nie muszą mieć postaci numerycznej: np. dane wynikowe 1/2 + 3 sqrt(5), -3/4 są z nią zgodne.
Właściwości algorytmów
Algorytmem nazwiemy ścisły przepis postępowania, którego wykonanie gwarantuje otrzymanie danych wynikowych z dostaczonych danych wejściowych w skończonym czasie zgodnie ze specyfikacją użytkową danego problemu. Szczegóły sformułowania algorytmu nie są przy tym związane bezpośrednio ze specyfiką wykonawcy, któremu zostanie zlecona jego realizacja. Algorytm stanowi ogólny schemat i może być zapisywany w różnych językach i konwencjach, zależnie od potrzeb, upodobań autora i wymagań wykonawcy. Oto podstawowe właściwości, którymi musi się cechować każdy algorytm:
zgodność ze specyfikacją
Algorytm jest rozwiązaniem problemu przetwarzania danych. Jeżeli nie postawiono problemu, nie ma sensu mówić o rozwiązaniu.
ogólność ze względu na wykonawcę
Sformułowanie algorytmu nie powinno korzystać ze specyficznych cech wykonawcy; w szczególności nie precyzuje się, czy jest on człowiekiem, czy maszyną.
jednoznaczność
W algorytmie nie ma miejsca na dowolność interpretacji; zamiast powiedzieć: weź dowolną wartość, trzeba określić sposób jej wyliczenia lub pobrania.
skończoność
Niezależnie od tego, czy liczba przewidzianych do wykonania czynności jest z góry znana, czy też zależy od danych, zapis poleceń musi być ujęty w skończonej formie.
generowanie wyników
Algorytm opisuje sposób otrzymania danych wynikowych. Celem realizacji algorytmu jest otrzymanie konkretnego wyniku. Algorytm, który nigdy nie daje żadnych wyników, jest równoważny niepodejmowaniu żadnej czynności.
Opis algorytmiczny nie może odwoływać się do wiedzy, inteligencji, doświadczenia wykonawcy; nie może też korzystać z analogii. W praktyce zakres wymaganych umiejętności wykonawcy bywa różny; najczęściej zakłada się, że umie on przeprowadzać obliczenia arytmetyczne, dokonywać operacji na danych innych typów (np. na napisach) oraz korzystać z danych otrzymanych drogą wykonania innych algorytmów.
Wymienione wyżej właściwości algorytmów mają charakter definiujący, tak więc musi posiadać je każdy algorytm. W praktyce cenione są algorytmy, które posiadają szereg dodatkowych, pożądanych właściwości. Oto najważniejsze z nich:
ogólność ze względu na dane
Sformułowanie algorytmu pozwala rozwiązać całą klasę podobnych zadań, różniących się parametrami ustalanymi za pośrednictwem danych wejściowych.
skuteczność
Dla każdego prawidłowego zestawu danych wejściowych algorytm powinien wyznaczyć odpowiednie dane wynikowe. Znaczenie pojęcia „prawidłowy zestaw danych” winno być wyjaśnione w specyfikacji danych; im szerszą klasę danych ono obejmuje, tym lepiej.
właściwość stopu
Dla możliwie szerokiej klasy danych wejściowych algorytm powinien zatrzymać się w skończonym czasie (po wykonaniu lub mimo niewykonania postawionego zadania).
efektywność
Algorytm powinien osiągać efekt końcowy możliwie niskim kosztem. Koszty eksploatacji są związane z czasem pracy wykonawcy: im bardziej efektywny algorytm, tym mniej czasu zajmie jego wykonanie temu samemu wykonawcy. Efektywność algorytmów wyraża się za pomocą pojęcia złożoności obliczeniowej; w najprostszym ujęciu charakteryzuje ona pracochłonność wykonania jako funkcję ilości danych wejściowych. Niestety — na ogół algorytmy bardziej efektywne są trudniejsze w realizacji, tym samym więcej czasu musi im poświęcić projektant i programista.
Przy rozwiązywaniu zadań praktycznych znaczenie ma również koszt opracowania i koszt przyszłej konserwacji algorytmu, mierzony wysiłkiem wkładanym w jego ulepszanie, rozbudowę oraz implementację w coraz to innych środowiskach. Algorytmy bardziej efektywne są często bardziej skomplikowane (więc trudniejsze w opracowaniu, analizie i implementacji).
-----------------------------------------------------------------------------------
Problemem stopu nazywamy sytuację, gdy dla danego algorytmu i danych wejściowych należy stwierdzić, czy program realizujący dany algorytm zatrzyma się.
Algorytm ma własność stopu, gdy dla każdych danych początkowych wykonane obliczenia są poprawne i skończone. Stosuje się różne reguły do oceny wnioskowania o stopie programu, np. kryterium liczników iteracji czy kryterium malejących wartości.
Nie zawsze jest możliwe rozstrzygnięcie. Np. dla poniższego algorytmu problem stopu nie został rozstrzygnięty.
-----------------------------------------------------------------------------------
Złożonośc obliczeniowa algorytmu
Złozonosc obliczeniowa algorytmu to ilosc zasobów komputerowych,
potrzebnych do jego wykonania. Zasoby komputerowe to czas działania i ilosc
zajmowanej pamieci.
Złozonosc czasowa algorytmu
Złozonosc czasowa algorytmu okresla „czas” realizacji algorytmu.
Złozonosc czasowa musi byc niezalezna od:
- szybkosci procesora, który wykonuje algorytm,
- wyboru jezyka programowania, w którym wykonana jest implementacja
algorytmu.
a) Rozmiar zadania
Rozmiar zadania (problemu) to rozmiar tych danych wejsciowych, których
ilosc wpływa na czas wykonania algorytmu, tzn. im wieksza jest ilosc tych
danych, tym dłuzej realizuje sie algorytm.
Przykład 2
Problem A1
WP: a1, a2, ..., an- ciag liczb całkowitych (n >0)
WK: Ciag a1, a2, ..., an posortowany niemalejaco
Rozmiar zadania: n – długosc ciagu, który nalezy posortowac
złozonosc
obliczeniowa
złozonosc czasowa złozonosc
pamieciowa
Problem A2
WP: a0, a1, ..., an- ciag liczb rzeczywistych (n ³ 0) definiujacy współczynniki
danego wielomianu W, x- dana liczba rzeczywista
WK: Liczba W(x) – wartosc wielomianu W dla argumentu x
Rozmiar zadania: n - stopien wielomianu W(x)
Problem A3
WP: t1, t2, ..., tn- ciag znaków tekstu (n > 0)
w1, w2, ..., wm- ciag znaków wzorca (n ³ m > 0)
WK: p- zmienna logiczna, która przyjmuje wartosc 1 (prawda), gdy wzorzec
wystepuje w tekscie, a 0 (fałsz), gdy wzorzec nie wystepuje w tekscie
Rozmiar zadania: n – długosc wzorca, m – długosc tekstu
b) operacja elementarna
Operacja elementarna (inaczej operacja dominujaca) to operacja
charakterystyczna dla danego algorytmu. To taka operacja, której łaczna liczba
wykonan jest proporcjonalna do rozmiaru zadania, tzn. im wiekszy rozmiar
zadania, tym wiecej razy realizuje sie operacja elementarna.
Przykład 3
Problem A1 - operacja elementarna jest operacja porównywania elementów
sortowanego ciagu albo operacja przestawiania elementów ciagu w czasie
sortowania.
Problem A2 - operacja elementarna jest operacja arytmetyczna mnoenia albo
operacja arytmetyczna dodawania realizowana w procesie obliczania wartosci
wielomianu dla danego x.
Problem A3 – operacja porównywania znaków wzorca ze znakami tekstu w
procesie sprawdzania, czy wzorzec wystepuje w tekscie.
Za jednostke złoonosci czasowej przyjmuje sie wykonanie jednej operacji
elementarnej (dominujacej). Złoonosc czasowa algorytmu jest funkcja
parametru (parametrów) rozmiaru zadania.
c) Złozonosc czasowa srednia i pesymistyczna
Nieformalnie
Złozonosc czasowa pesymistyczna to ilosc wykonanych operacji elementarnych
dla danych „najgorszego” przypadku
Złozonosc czasowa oczekiwana to ilosc wykonanych operacji elementarnych dla
danych „typowego” przypadku.
Poprawnosc całkowita i czesciowa algorytmu
Definicja 1
Algorytm A jest czesciowo poprawny wzgledem danego warunku WP i danego
warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejsciowych
spełniajacych warunek WP, jezeli algorytm A zatrzymuje sie, to dane
wyjsciowe algorytmu spełniaja warunek WK.
Definicja 2
Algorytm A jest całkowicie poprawny wzgledem danego warunku WP i danego
warunku WK wtedy i tylko wtedy, gdy dla dowolnych danych wejsciowych
spełniajacych warunek WP algorytm A zatrzymuje sie i dane wyjsciowe tego
algorytmu spełniaja warunek WK.
Przykład 1
Formalny zapis WP i WK
WP: n>0 Ù nÎN
WK: (s=1+3+5+...+n Ù n mod 2¹0) Ú (s=1+3+5+...+n-1 Ù n mod 2=0)
Nieformalna specyfikacja WP i WK
WP: n – liczba naturalna wieksza od zera
WK: s – suma kolejnych liczb nieparzystych nie wiekszych niz n
Algorytm (pseudokod)
s=0; i=1;
while (i!=n+2)
{
s=s + i;
i+=2;
};
Powyzszy algorytm jest poprawny czesciowo, ale nie całkowicie. Dla n
parzystego petla nie ma stopu, ale dla dowolnego n nieparzystego petla konczy
sie po skonczonej liczbie kroków i wartosc koncowa zmiennej s spełnia WK.
Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.
Przykładowe struktury danych to:
* rekord, zwany w niektórych językach po prostu strukturą (ang. struct, record), logiczny odpowiednik to krotka
* tablica
* lista
* stos
* kolejka
* drzewo i jego liczne odmiany (np. drzewo binarne)
* graf
Podczas implementacji programu programista często staje przed wyborem między różnymi strukturami danych, aby uzyskać pożądany efekt. Odpowiedni wybór może zmniejszyć złożoność obliczeniową, ale z drugiej strony trudność implementacji danej struktury może stanowić istotną przeszkodę.
Ponieważ struktury danych są w programie rzeczą szczególnie istotną, wiele języków programowania wspiera programistę, dostarczając bibliotekę standardową z zaimplementowanymi różnorodnymi strukturami danych. Można tu wymienić Standard Template Library w C++, API języka Java oraz platformę .NET.
Próbą połączenia idei struktur danych i algorytmów jest pomysł programowania obiektowego.
Dowód poprawności algorytmu
Dowód poprawności algorytmu jest rozumowaniem matematycznym prowadzącym do formalnego wykazania, że dany algorytm przy poprawnych danych wejściowych da nam wynik spełniający wymagania, np. że algorytm quicksort po podaniu mu niepustej tablicy elementów porównywalnych na wyjściu da nam tablicę zawierającą te same elementy, ale uporządkowane w kolejności od najmniejszego do największego.
Dowód poprawności algorytmu zawsze składa się z dwóch części:
* dowód, że jeśli algorytm się zakończy, to da poprawny wynik,
* dowód, że przy poprawnych danych wejściowych algorytm zawsze się zakończy.
Do dowodzenia poprawności algorytmów wykorzystywane są zazwyczaj pewne formalizmy matematyczne wiążące ze sobą warunek wstępny, kod oraz warunek końcowy. Większość tych formalizmów opiera się o logikę Hoare'a.
W ogólnym przypadku pytanie, czy dany algorytm jest poprawny jest nierozstrzygalne, dla większości języków opisu algorytmów nierozstrzygalne są nawet pytania:
* czy dane dwa algorytmy dają taki sam wynik,
* czy dany algorytm dla poprawnych danych wejściowych się kończy (nawet przy założeniu, że zawsze jesteśmy w stanie zweryfikować poprawność danych wejściowych).
Są jednak takie języki w których np. da się udzielić odpowiedzi na drugie pytanie. Do takich języków należą np. niektóre z odmian rachunku lambda takie jak System F.
Teoria obliczeń
Dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.
Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu rozumieć jako komputer o nieograniczonych zasobach pamięci.
Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich da się też obliczyć na maszynie Turinga.
Rozważa się również węższe modele (tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej).
* funkcje pierwotnie rekurencyjne
O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga, czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia się zatrzyma
Teoria złożoności obliczeniowej
Dział teorii obliczeń. Głównym jej celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów. Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać: problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji i wiele innych, jednak takich, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, która jest drugą ważną gałęzią teorii obliczeń.
Wyniki, jakie podaje t.z.o. można podzielić na dwie kategorie: pozytywne i negatywne; w uproszczeniu na takie, które podają co i jak da się obliczyć oraz takie, w których dowodzi się czego nie da się obliczyć wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.
Złożoność algorytmów
Ilość zasobów potrzebnych dla działania algorytmu może być rozumiana jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej lub pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od instancji problemu.
Jako przykład może nam posłużyć problem rozkładu liczb na czynniki pierwsze. Domyślamy się, że (niezależnie od algortymu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Taką własność ma znakomita większość problemów obliczeniowych: im większy rozmiar danych wejściowych tym więcej zasobów (czasu, procesorów, pamięci) jest potrzebnych do jego rozwiązania. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.
Kolejnym problemem jest fakt, iż złożoność zwykle nie zależy tylko i wyłącznie od rozmiaru danych, ale może się znacznie różnić dla instancji o identycznym rozmiarze. Dwa często spotykane sposoby radzenia sobie z tym problemem to: branie pod uwagę przypadków najgorszych (złożoność pesymistyczna) i pewien sposób uśrednienia wszystkich możliwych przypadków (złożoność oczekiwana).
Złożoność czasowa
Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od implementacji algorytmu, użytego kompilatora, maszyny na której algorytm wykonano, a także umiejętności programisty. Dlatego w charakterze czasu wykonania rozpatrujemy zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.
Kolejny problem polega na tym, w jakim języku programowania formułować algorytmy oraz co można założyć o maszynie, na której algorytm ten będzie wykonywany. Istniejące komputery różnią się między sobą istotnymi (z punktu widzenia konstruowania algorytmów) parametrami, jak na przykład liczba i rozmiar rejestrów, udostępnianymi operacjami matematycznymi a ponadto podlegają ciągłym ulepszeniom. Wobec tego algorytmy analizuje się wykorzystując abstrakcyjne modele komputera. Do popularnych modeli należą maszyna wskaźnikowa i maszyna RAM.
Złożoność pamięciowa
Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć maszyny abstakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej wyrażonej w bitach lub bajtach).
Porównywanie złożoności algorytmów
Porównując złożoność algorytmów bierzemy pod uwagę asymptotyczne tempo wzrostu, czyli to jak zachowuje się funkcja określająca złożoność dla odpowiedniu dużych, granicznych argumentów (rozmiarów danych wejściowych) ignorując zachowanie dla małych danych. Ponadto złożoności algorytmów różniące się o stałą uważamy za takie same, co eliminuje wpływ szybkości działania komputera, na którym dany algorytm ma być wykonany oraz wybór operacji podstawowej, która na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zastąpiona szeregiem instrukcji.
Klasy złożoności
Klasa złożoności to zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej - innymi słowy problemy do których rozwiązania potrzebna jest podobna ilość zasobów łączymy w klasy. Przykładowo mówimy o problemach o liniowej złożoności pamięciowej, jeśli ilość potrzebnej pamięci rośnie liniowo względem rozmiaru danych; czy też o problemach o kwadratowej złożoności czasowej, jeśli liczba operacji podstawowyych rośnie z kwadratem rozmiaru danych. Podobne określenia stosujemy do algorytmów.
Stosujemy też szersze pojęcia takie jak klasa P, czy NP mając odpowiedno na uwadze decyzyjne problemy wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
Teoria obliczeń to Dział informatyki teoretycznej. Dzieli się on na dwie główne części: teorię obliczalności (W informatyce teoretycznej teoria obliczalności to dział teorii obliczeń zajmujący się stwierdzaniem, które problemy obliczeniowe dadzą się rozwiązać, a które nie) oraz złożoność obliczeniową. Pierwszy z nich zajmuje się odpowiedzią na pytanie, które problemy dają się rozwiązać przy pomocy komputera, a drugi tym jak szybko da się to zrobić.
Rozważania tego typu nie są możliwe bez formalnego, matematycznego modelu komputera. Najczęściej używanym modelem jest maszyna Turinga. Taką maszynę można w uproszczeniu rozumieć jako komputer o nieograniczonych zasobach pamięci.
Inne używane modele, takie jak: rachunek lambda, rachunek kombinatorów, algorytmy Markowa, funkcje rekurencyjne są sobie równoważne w tym sensie, że wszystko co jest obliczalne na jednym z nich da się też obliczyć na maszynie Turinga.
Rozważa się również węższe modele (tzn. takie, które nie pozwalają na wyrażenie dowolnej funkcji obliczalnej).
* funkcje pierwotnie rekurencyjne
O niektórych problemach związanych z modelami obliczeń wiadomo, że są nierozstrzygalne. Na przykład nie istnieje algorytm, który rozstrzyga, czy dwa λ-wyrażenia są równoważne lub czy maszyna Turinga dla danego wejścia się zatrzyma.