ANALIZA ALGORYTMÓW | NOTACJA DUŻA - Θ (DUŻA THETA) - TECHCODEVIEW.COM

w analiza algorytmów , notacje asymptotyczne służą do oceny wydajności algorytmu najlepsze i najgorsze przypadki . W artykule omówione zostaną notacje Big – Theta reprezentowane przez grecką literę (Θ).

Definicja: Niech g i f będą funkcją ze zbioru liczb naturalnych do samej siebie. Mówi się, że funkcja f to Θ(g), jeśli istnieją stałe c₁, C₂> 0 i liczba naturalna n₀tak, że c₁* g(n) ≤ f(n) ≤ do₂* g(n) dla wszystkich n ≥ n₀

Reprezentacja matematyczna:

Θ (g(n)) = {f(n): istnieją stałe dodatnie c₁, C₂oraz n₀takie, że 0 ≤ c₁* g(n) ≤ f(n) ≤ do₂* g(n) dla wszystkich n ≥ n₀}
Uwaga: Θ(g) jest zbiorem

Powyższa definicja oznacza, że jeśli f(n) jest teta g(n), to wartość f(n) zawsze mieści się w przedziale od c1 * g(n) do c2 * g(n) dla dużych wartości n (n ≥ n₀). Definicja theta wymaga również, aby f(n) było nieujemne dla wartości n większych niż n₀.

10 potęga 6

Reprezentacja graficzna:

Reprezentacja graficzna

W prostym języku notacja Big – Theta(Θ) określa asymptotyczne granice (zarówno górne, jak i dolne) funkcji f(n) i podaje średnią złożoność czasową algorytmu.

Wykonaj poniższe kroki, aby znaleźć średnią złożoność czasową dowolnego programu:

Podziel program na mniejsze segmenty.
Znajdź wszystkie typy i liczbę wejść oraz oblicz liczbę operacji potrzebnych do wykonania. Upewnij się, że przypadki wejściowe są równomiernie rozłożone.
Znajdź sumę wszystkich obliczonych wartości i podziel ją przez całkowitą liczbę wejść, powiedzmy, że otrzymana funkcja n to g(n) po usunięciu wszystkich stałych, wówczas w notacji Θ jest ona reprezentowana jako Θ(g(n))

Przykład: Rozważmy przykład sprawdź, czy klucz istnieje w tablicy, czy nie, używając wyszukiwania liniowego . Pomysł jest taki przemierzać tablicę i sprawdź każdy element, czy jest równy kluczowi, czy nie.

np. wyjątkowy

Pseudokod wygląda następująco:

bool linearSearch(int a[], int n, int key) {  for (int i = 0; i   if (a[i] == key)  return true;  }   return false; }>

Poniżej implementacja powyższego podejścia:

C++

// C++ program for the above approach> #include> using> namespace> std;> // Function to find whether a key exists in an> // array or not using linear search> bool> linearSearch(>int> a[],>int> n,>int> key)> {> >// Traverse the given array, a[]> >for> (>int>

i = 0; i   // Check if a[i] is equal to key  if (a[i] == key)  return true;  }  return false; } // Driver Code int main() {  // Given Input  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = sizeof(arr) / sizeof(arr[0]);  // Function Call    if (linearSearch(arr, n, x))  cout << 'Element is present in array';  else  cout << 'Element is not present in array';  return 0; }>

Jawa

// Java program for the above approach> import> java.lang.*;> import> java.util.*;> class> GFG{> // Function to find whether a key exists in an> // array or not using linear search> static> boolean> linearSearch(>int> a[],>int> n,> >int> key)> {> > >// Traverse the given array, a[]> >for>(>int> i =>0>

; i   {    // Check if a[i] is equal to key  if (a[i] == key)  return true;  }  return false; } // Driver code public static void main(String[] args) {    // Given Input  int arr[] = { 2, 3, 4, 10, 40 };  int x = 10;  int n = arr.length;  // Function Call  if (linearSearch(arr, n, x))  System.out.println('Element is present in array');  else  System.out.println('Element is not present in array'); } } // This code is contributed by avijitmondal1998>

Python3

# Python3 program for the above approach> # Function to find whether a key exists in an> # array or not using linear search> def> linearSearch(a, n, key):> ># Traverse the given array, a[]> >for> i>in> range>(>0>, n):> ># Check if a[i] is equal to key> >if> (a[i]>=>=> key):> >return> True> > >return> False> # Driver Code> # Given Input> arr>=> 2>,>3>,>4>,>10>,>40> x>=> 10> n>=> len>(arr)> # Function Call> if> (linearSearch(arr, n, x)):> >print>(>'Element is present in array'>)> else>:> >print>(>'Element is not present in array'>)> > # This code is contributed by shivanisinghss2110>

C#

// C# program for above approach> using> System;> class> GFG{> // Function to find whether a key exists in an> // array or not using linear search> static> bool> linearSearch(>int>[] a,>int> n,> >int> key)> {> > >// Traverse the given array, a[]> >for>(>int>

i = 0; i   {    // Check if a[i] is equal to key  if (a[i] == key)  return true;  }  return false; } // Driver Code static void Main() {  // Given Input  int[] arr = { 2, 3, 4, 10, 40 };  int x = 10;  int n = arr.Length;  // Function Call  if (linearSearch(arr, n, x))  Console.Write('Element is present in array');  else  Console.Write('Element is not present in array'); } } // This code is contributed by sanjoy_62.>

JavaScript

> // JavaScript program for the above approach> // Function to find whether a key exists in an> // array or not using linear search> function> linearSearch(a, n, key)> {> > >// Traverse the given array, a[]> >for>(>var>

i = 0; i   {    // Check if a[i] is equal to key  if (a[i] == key)  return true;  }  return false; } // Driver code  // Given Input  var arr = [ 2, 3, 4, 10, 40 ];  var x = 10;  var n = arr.length;  // Function Call  if (linearSearch(arr, n, x))  document.write('Element is present in array');  else  document.write('Element is not present in array'); // This code is contributed by shivanisinghss2110>

Wyjście

Element is present in array>

Złożoność czasowa: NA)
Przestrzeń pomocnicza: O(1)

W przypadku problemu poszukiwania liniowego załóżmy, że wszystkie przypadki są takie równomiernie rozłożone (również w przypadku braku klucza w tablicy). Zatem zsumuj wszystkie przypadki (kiedy klucz jest obecny na pozycji 1, 2, 3, ……, n i nie występuje, i podziel sumę przez n + 1.

Średnia złożoność czasowa sprawy = $frac{sum_{i=1}^{n+1} heta(i)}{n + 1}$

⇒ $frac{ heta((n+1)*(n+2)/2)}{n+1}$

⇒

⇒ (stałe są usuwane)
Java len tablicy

Kiedy stosować notację Big – Θ: Big – Θ analizuje algorytm z największą dokładnością, ponieważ przy obliczaniu Big – Θ uwzględniany jest równomierny rozkład różnych typów i długości wejść, podaje średnią złożoność czasową algorytmu, która jest najdokładniejsza przy analizie, jednak w praktyce czasami w takim przypadku trudno jest znaleźć równomiernie rozłożony zestaw danych wejściowych dla algorytmu, Notacja dużego O używany jest, który reprezentuje asymptotyczną górną granicę funkcji f .

Więcej szczegółów znajdziesz w: Projektowanie i analiza algorytmów .

TechCodeview

Analiza algorytmów | Notacja duża – Θ (duża theta).

C++

Jawa

Python3

C#

JavaScript