Przejdź do treści

Wzory z informatyki

Działy

Algorytmy i złożoność · Liczba operacji

Model kwadratowej liczby operacji

T = a n^{2} + bn + c

zakres rozszerzony, na studiach (I–II rok)

2 zadania Gdy brakuje danej Policz z innych danych

Kiedy można użyć wzoru

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.

Co oznaczają symbole

$T$ liczba operacji dla danych o rozmiarze n
$a, b, c$ stałe współczynniki modelu liczby operacji
$n$ rozmiar danych wejściowych

Przekształcenia

$a = \frac{T - nb - c}{n ^{2}}$ krok po kroku
1. Wzór wyjściowy
  $T = a n^{2} + bn + c$
2. Zamieniamy strony
  $a n^{2} + bn + c = T$
3. Odejmujemy $nb + c$ od obu stron
  $a n^{2} = T - nb - c$
4. Dzielimy obie strony przez $n^{2}$
  $a = \frac{T - nb - c}{n ^{2}}$
$b = \frac{T - a n ^{2} - c}{n}$ krok po kroku
1. Wzór wyjściowy
  $T = a n^{2} + bn + c$
2. Zamieniamy strony
  $a n^{2} + bn + c = T$
3. Odejmujemy $a n^{2} + c$ od obu stron
  $nb = T - a n^{2} - c$
4. Dzielimy obie strony przez $n$
  $b = \frac{T - a n ^{2} - c}{n}$
$c = T - a n^{2} - nb$ krok po kroku
1. Wzór wyjściowy
  $T = a n^{2} + bn + c$
2. Zamieniamy strony
  $a n^{2} + bn + c = T$
3. Odejmujemy $a n^{2} + nb$ od obu stron
  $c = T - a n^{2} - nb$

336×280Tu może być Twoja reklama

Sprawdzenie jednostek

Po podstawieniu jednostek SI obie strony wzoru muszą dać to samo.

$[1] = 1$

Gdy brakuje danej

Jeśli w zadaniu nie ma którejś wielkości, policz ją najpierw z innego wzoru.

$T$ liczba operacji dla danych o rozmiarze n $T = an + b$ ze wzoru model liniowej liczby operacji
$a$ stałe współczynniki modelu liczby operacji $a = \frac{T - b}{n}$ ze wzoru model liniowej liczby operacji
$n$ rozmiar danych wejściowych $n = \frac{T - b}{a}$ ze wzoru model liniowej liczby operacji
$b$ stałe współczynniki modelu liczby operacji $b = T - an$ ze wzoru model liniowej liczby operacji

Zadania krok po kroku

Gdy w zadaniu brakuje którejś wielkości z tego wzoru, łączysz go z innym. Otwórz zadanie, żeby zobaczyć kroki.

Jak obliczyć stałe współczynniki modelu liczby operacji, mając liczbę operacji dla danych o rozmiarze n, stałe współczynniki modelu liczby operacji i stałe współczynniki modelu liczby operacji $c = \frac{T ( a + b - T )}{a}$
Dane
$T$ liczba operacji dla danych o rozmiarze n $a$ stałe współczynniki modelu liczby operacji $b$ stałe współczynniki modelu liczby operacji
Szukane
$c$ stałe współczynniki modelu liczby operacji
1. ze wzoru model liniowej liczby operacji
  $n = \frac{T - b}{a}$
2. ze wzoru model kwadratowej liczby operacji
  $c = T - a n^{2} - nb$
Jednostki $[1] = 1$
Jak obliczyć stałe współczynniki modelu liczby operacji, mając stałe współczynniki modelu liczby operacji, rozmiar danych wejściowych i stałe współczynniki modelu liczby operacji $c = an + b - a n^{2} - nb$
Dane
$a$ stałe współczynniki modelu liczby operacji $n$ rozmiar danych wejściowych $b$ stałe współczynniki modelu liczby operacji
Szukane
$c$ stałe współczynniki modelu liczby operacji
1. ze wzoru model liniowej liczby operacji
  $T = an + b$
2. ze wzoru model kwadratowej liczby operacji
  $c = T - a n^{2} - nb$
Jednostki $[1] = 1$

W podstawie programowej

Zakres rozszerzony, I.5: Uczeń objaśnia dobrany algorytm, uzasadnia poprawność rozwiązania na wybranych przykładach danych i ocenia jego efektywność.

728×280Tu może być Twoja reklama

Policz z innych danych Wszystkie wzory działu Algorytmy i złożoność