En el anàlisi d'algorismes , les notacions asimptòtiques s'utilitzen per avaluar el rendiment d'un algorisme, en el seu millors i pitjors casos . Aquest article parlarà de les notacions Big - Theta representades per una lletra grega (Θ).
Definició: Siguin g i f la funció del conjunt de nombres naturals a si mateix. Es diu que la funció f és Θ(g), si hi ha constants c1, c2> 0 i un nombre natural n0tal que c1* g(n) ≤ f(n) ≤ c2* g(n) per a tot n ≥ n0
Representació matemàtica:
Θ (g(n)) = {f(n): existeixen constants positives c1, c2i n0tal que 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) per a tot n ≥ n0}
Nota: Θ(g) és un conjunt
La definició anterior vol dir que si f(n) és theta de g(n), aleshores el valor f(n) sempre està entre c1 * g(n) i c2 * g(n) per a valors grans de n (n ≥ n).0). La definició de theta també requereix que f(n) ha de ser no negatiu per a valors de n majors que n0.
rebaixa amb imatges
Representació gràfica:
Representació Gràfica
En llenguatge senzill, la notació Big – Theta(Θ) especifica els límits asimptòtics (tant superiors com inferiors) per a una funció f(n) i proporciona la complexitat temporal mitjana d'un algorisme.
Seguiu els passos següents per trobar la complexitat mitjana del temps de qualsevol programa:
- Dividiu el programa en segments més petits.
- Troba tots els tipus i nombre d'entrades i calcula el nombre d'operacions que necessiten per executar-se. Assegureu-vos que els casos d'entrada estiguin distribuïts per igual.
- Trobeu la suma de tots els valors calculats i dividiu la suma pel nombre total d'entrades, diguem que la funció de n obtinguda és g(n) després d'eliminar totes les constants, llavors en notació Θ es representa com Θ(g(n))
Exemple: Considereu un exemple Trobeu si una clau existeix en una matriu o no utilitzant la cerca lineal . La idea és fer travessa la matriu i comproveu cada element si és igual a la clau o no.
El pseudocodi és el següent:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>A continuació es mostra la implementació de l'enfocament anterior:
desinstal·leu angular cli
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; }> |
>
>
Java
// 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> |
>
>
Python 3
# 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> |
>
>
Sortida
Element is present in array>
Complexitat temporal: O(n)
Espai auxiliar: O(1)
En un problema de cerca lineal, suposem que tots els casos ho són distribuïts uniformement (inclòs el cas en què la clau està absent a la matriu). Per tant, sumeu tots els casos (quan la clau està present a la posició 1, 2, 3, ……, n i no està present, i divideix la suma per n + 1.
cadena en java
Complexitat mitjana del temps del cas =
⇒
⇒
⇒
(s'eliminen les constants)
Quan utilitzar la notació Big – Θ: Big – Θ analitza un algorisme amb la precisió més precisa, ja que mentre es calcula Big – Θ, es considera una distribució uniforme de diferents tipus i longitud de les entrades, proporciona la complexitat mitjana del temps d'un algorisme, que és més precisa durant l'anàlisi, però a la pràctica. de vegades es fa difícil trobar el conjunt uniformement distribuït d'entrades per a un algorisme, en aquest cas, Notació Big-O s'utilitza que representen el límit superior asimptòtic d'una funció f.
Per a més detalls, consulteu: Disseny i anàlisi d'algorismes .