Algorytmy i złożoność

Złożoność opisuje, jak rośnie nakład pracy algorytmu wraz z rozmiarem danych n. Współczynniki i składniki niższego rzędu nie zmieniają klasy wzrostu dla dużych n.

Liczba operacji

model liniowej liczby operacji: $T = an + b$; zakres rozszerzony, wzór kluczowy; gdzie:
$T$ liczba operacji dla danych o rozmiarze n
$a, b$ stałe współczynniki modelu liczby operacji
$n$ rozmiar danych wejściowych
Strona wzoru: przekształcenia i jednostki
model kwadratowej liczby operacji: $T = a n^{2} + bn + c$; zakres rozszerzony; gdzie:
$T$ liczba operacji dla danych o rozmiarze n
$a, b, c$ stałe współczynniki modelu liczby operacji
$n$ rozmiar danych wejściowych
Strona wzoru: przekształcenia i jednostki

Obliczenia równoległe

prawo Amdahla: $S = \frac{1}{( 1 - p ) + \frac{p}{s}}$; poza podstawą programową; gdzie:
$S$ przyspieszenie: czas sekwencyjny podzielony przez czas równoległy
$p$ część obliczeń, którą można wykonać równolegle (od 0 do 1)
$s$ przyspieszenie części równoległej
Strona wzoru: jednostki

336×280Tu może być Twoja reklama

Algorytmy liczbowe

schemat Hornera dla wielomianu: $b_{n} = a_{n}, b_{k} = a_{k} + x b_{k + 1}, W (x) = b_{0}$; zakres rozszerzony; gdzie:
$b_{n}$ początkowy akumulator Hornera $1$
$a_{n}$ współczynnik najwyższej potęgi wielomianu $1$
$b_{k}$ akumulator Hornera po kroku k $1$
$a_{k}$ współczynnik k-tej potęgi wielomianu $1$
$x$ argument wielomianu $1$
$b_{k + 1}$ akumulator Hornera przed krokiem k $1$
$W$ wielomian $1$
$b_{0}$ końcowa wartość wielomianu $1$
Strona wzoru
krok algorytmu Euklidesa: $g cd (a, b) = g cd (b, a mod b)$; zakres podstawowy; gdzie:
$a, b$ stałe współczynniki modelu liczby operacji
Strona wzoru
najmniejsza wspólna wielokrotność: $NWW (a, b) = \frac{ab}{g cd ( a , b )}$; zakres podstawowy; gdzie:
$a, b$ stałe współczynniki modelu liczby operacji
Strona wzoru
rekurencja ciągu Fibonacciego: $F_{0} = 0, F_{1} = 1, F_{n} = F_{n - 1} + F_{n - 2}$; zakres podstawowy; gdzie:
$F_{0}$ wyraz zerowy ciągu Fibonacciego $1$
$F_{1}$ pierwszy wyraz ciągu Fibonacciego $1$
$F_{n}$ n-ty wyraz ciągu Fibonacciego $1$
$F_{n - 1}$ poprzedni wyraz ciągu Fibonacciego $1$
$F_{n - 2}$ drugi poprzedni wyraz ciągu Fibonacciego $1$
Strona wzoru

Prawa i uwagi

Notacja asymptotyczna

Model T(n) = an + b ma wzrost liniowy, czyli O(n). Model T(n) = an² + bn + c ma wzrost kwadratowy, czyli O(n²). W pierwszym modelu zakładamy a > 0, w drugim a > 0. Przy zerowym współczynniku wiodącym stopień wzrostu może być niższy. Notacja O jest ograniczeniem górnym; dla tych modeli z dodatnim współczynnikiem wiodącym dokładniejszą klasą jest odpowiednio Θ(n) i Θ(n²). To modele liczby operacji, a nie uniwersalne wzory na czas dowolnego algorytmu.

Prawo Amdahla

p jest częścią programu, którą można zrównoleglić, a s przyspieszeniem tej części. Wzór zakłada niezmienioną, szeregową część programu; nawet nieskończenie szybka część równoległa ogranicza przyspieszenie do 1/(1 − p), jeśli p < 1. Gdy p = 1, S = s i nie ma skończonej granicy przy s rosnącym bez ograniczeń. Przyjmujemy 0 ≤ p ≤ 1 i s ≥ 1, bez narzutu komunikacji.

Symbole i jednostki

symbol	znaczenie	jednostka SI	nazwa
$T$	liczba operacji dla danych o rozmiarze n	$-$	operacja
$n$	rozmiar danych wejściowych	$-$	element
$a, b, c$	stałe współczynniki modelu liczby operacji	$-$	współczynnik
$S$	przyspieszenie: czas sekwencyjny podzielony przez czas równoległy	$-$	bez jednostki
$p$	część obliczeń, którą można wykonać równolegle (od 0 do 1)	$-$	ułamek
$s$	przyspieszenie części równoległej	$-$	bez jednostki
$a_{n}$	współczynnik najwyższej potęgi wielomianu	$1$	bez jednostki
$a_{k}$	współczynnik k-tej potęgi wielomianu	$1$	bez jednostki
$b_{n}$	początkowy akumulator Hornera	$1$	bez jednostki
$b_{k}$	akumulator Hornera po kroku k	$1$	bez jednostki
$b_{k + 1}$	akumulator Hornera przed krokiem k	$1$	bez jednostki
$b_{0}$	końcowa wartość wielomianu	$1$	bez jednostki
$x$	argument wielomianu	$1$	bez jednostki
$W$	wielomian	$1$	bez jednostki
$a$	pierwszy argument NWD i NWW	$1$	bez jednostki
$b$	drugi argument NWD i NWW	$1$	bez jednostki
$F_{n}$	n-ty wyraz ciągu Fibonacciego	$1$	bez jednostki
$F_{n - 1}$	poprzedni wyraz ciągu Fibonacciego	$1$	bez jednostki
$F_{n - 2}$	drugi poprzedni wyraz ciągu Fibonacciego	$1$	bez jednostki
$F_{0}$	wyraz zerowy ciągu Fibonacciego	$1$	bez jednostki
$F_{1}$	pierwszy wyraz ciągu Fibonacciego	$1$	bez jednostki

Oznaczenia

zakres podstawowy: według podstawy programowej z 2024 r.
zakres rozszerzony: zakres rozszerzony podstawy programowej informatyki
poza podstawą programową: od 2025 r. nie jest wymagany na maturze
wzór kluczowy: najczęściej potrzebny na sprawdzianach i maturze; zakreślony na ekranie, z gwiazdką na wydruku

Zakres wynika z wymagań podstawy programowej; numery wymagań są na stronie każdego wzoru.

728×280Tu może być Twoja reklama