Studia informatyka – Złożoność obliczeniowa

Złożoność czasowa

Określa czas potrzebny na zakończenie algorytmu w zależności od wielkości wejścia.

Złożoność przestrzenna

Mierzy ilość pamięci wymaganej przez algorytm w zależności od wielkości wejścia.

Klasyfikacja algorytmów

Algorytmy klasyfikowane są według złożoności: stała, logarytmiczna, liniowa, kwadratowa, itd.

Prawda czy fałsz: Złożoność czasowa algorytmu może być stała.

Prawda, ponieważ niektóre algorytmy wykonują stałą liczbę operacji.

Różnica między O(n) a O(n^2)

O(n) oznacza liniową złożoność, podczas gdy O(n^2) oznacza kwadratową złożoność, co jest mniej efektywne.

Algorytm liniowy

Jego złożoność czasowa wynosi O(n), co oznacza, że czas działania rośnie liniowo z rozmiarem danych.

Złożoność logarytmiczna

Oznaczona jako O(log n), wskazuje, że czas działania algorytmu rośnie wolniej niż liniowo.

Moc obliczeniowa

Zdolność systemu komputerowego do wykonania złożonych obliczeń w określonym czasie.

Wielomiany

Wszystkie funkcje o złożoności O(n^k) są uważane za złożoności wielomianowe.

Uzupełnij zdanie: Złożoność algorytmu sortowania bąbelkowego wynosi ___

O(n^2), co czyni go mało efektywnym dla dużych zbiorów danych.

Algorytmy NP

Klasa problemów, dla których rozwiązanie można zweryfikować w czasie wielomianowym.

Prawda czy fałsz: O(1) oznacza złożoność stałą.

Prawda, ponieważ oznacza, że liczba operacji nie zmienia się względem rozmiaru danych.

Złożoność wykładnicza

Oznaczona jako O(2^n), wskazuje na dramatyczny wzrost czasu działania przy wzroście rozmiaru danych.

Problem P

Klasa problemów, które można rozwiązać w czasie wielomianowym.

Algorytmy zachłanne

Strategia, która podejmuje lokalnie optymalne decyzje w celu znalezienia globalnego optimum.

Prawda czy fałsz: Algorytm o złożoności O(n log n) jest bardziej efektywny niż O(n^2).

Prawda, ponieważ O(n log n) rośnie wolniej niż O(n^2) dla dużych n.

Różnica między złożonością czasową a przestrzenną

Czasowa odnosi się do czasu wykonania, a przestrzenna do pamięci używanej przez algorytm.

Uzupełnij zdanie: Algorytm QuickSort ma średnią złożoność ___

O(n log n), co czyni go efektywnym algorytmem sortowania.

Złożoność sterowania

Odnosimy się do złożoności struktury kontrolnej algorytmu, np. pętli czy warunków.

Co to jest problem NP-trudny?

Klasa problemów, które są co najmniej tak trudne jak najtrudniejsze problemy NP.

Algorytm Dijkstry

Służy do znajdowania najkrótszej ścieżki w grafie o nieujemnych wagach.

Uzupełnij zdanie: Wzrost złożoności wykładniczej prowadzi do ___

Szybkiego wzrostu czasu obliczeń, co czyni algorytmy niepraktycznymi dla dużych danych.

Prawda czy fałsz: Każdy problem NP można rozwiązać w czasie wielomianowym.

Fałsz, ponieważ nie udowodniono, że P=NP.

Złożoność algorytmu BFS

O(n + m), gdzie n to liczba wierzchołków, a m to liczba krawędzi w grafie.

Zastosowanie algorytmu A*

Stosowany w grafach do znajdowania najkrótszej trasy z uwzględnieniem heurystyk.

Co to jest złożoność asymptotyczna?

Analiza zachowania algorytmu w miarę wzrostu rozmiaru wejścia.

Różnica między złożonością O(n) a O(n^2)

O(n) rośnie liniowo, O(n^2) kwadratowo, co sprawia, że O(n) jest bardziej efektywne.

Złożoność falkowa

Dotyczy algorytmów, które mają zmienną złożoność w różnych warunkach wejściowych.

Algorytm MergeSort

Działa na zasadzie dziel i zwyciężaj, z złożonością O(n log n) w najgorszym przypadku.