Dans le analyse d'algorithmes , les notations asymptotiques sont utilisées pour évaluer les performances d'un algorithme, dans son meilleurs cas et pires cas . Cet article discutera des notations Big – Theta représentées par une lettre grecque (Θ).
Définition: Soit g et f la fonction de l'ensemble des nombres naturels vers lui-même. La fonction f est dite Θ(g), s'il existe des constantes c1, c2> 0 et un entier naturel n0tel que c1* g(n) ≤f(n) ≤c2* g(n) pour tout n ≥ n0
Représentation mathématique :
Θ (g(n)) = {f(n) : il existe des constantes positives c1, c2et n0tel que 0 ≤ c1* g(n) ≤f(n) ≤c2* g(n) pour tout n ≥ n0}
Remarque : Θ(g) est un ensemble
La définition ci-dessus signifie que si f(n) est thêta de g(n), alors la valeur f(n) est toujours comprise entre c1 * g(n) et c2 * g(n) pour les grandes valeurs de n (n ≥ n0). La définition de thêta exige également que f(n) soit non négatif pour les valeurs de n supérieures à n0.
tri à bulles python
Représentation graphique:
Représentation graphique
En langage simple, la notation Big – Theta(Θ) spécifie les limites asymptotiques (à la fois supérieures et inférieures) pour une fonction f(n) et fournit la complexité temporelle moyenne d'un algorithme.
Suivez les étapes ci-dessous pour connaître la complexité temporelle moyenne de n'importe quel programme :
- Divisez le programme en segments plus petits.
- Recherchez tous les types et nombres d’entrées et calculez le nombre d’opérations nécessaires à leur exécution. Assurez-vous que les cas d’entrée sont répartis de manière égale.
- Trouvez la somme de toutes les valeurs calculées et divisez la somme par le nombre total d'entrées, disons que la fonction de n obtenue est g(n) après avoir supprimé toutes les constantes, puis en notation Θ, elle est représentée par Θ(g(n))
Exemple: Prenons un exemple pour déterminer si une clé existe dans un tableau ou non en utilisant la recherche linéaire . L'idée est de parcourir le tableau et vérifiez chaque élément s'il est égal à la clé ou non.
police latex
Le pseudo-code est le suivant :
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
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> |
>
>
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> |
>
>
Sortir
Element is present in array>
Complexité temporelle : Sur)
Espace auxiliaire : O(1)
Dans un problème de recherche linéaire, supposons que tous les cas sont uniformément réparti (y compris le cas où la clé est absente du tableau). Alors, additionnez tous les cas (lorsque la clé est présente en position 1, 2, 3, ……, n et non présente, et divisez la somme par n + 1.
Complexité moyenne de la durée d'un dossier =
⇒
⇒
⇒
(les constantes sont supprimées)
combien de villes y a-t-il aux États-Unis
Quand utiliser la notation Big – Θ : Big – Θ analyse un algorithme avec la précision la plus précise car lors du calcul de Big – Θ, une distribution uniforme de différents types et longueurs d'entrées est prise en compte, il fournit la complexité temporelle moyenne d'un algorithme, qui est la plus précise lors de l'analyse, mais en pratique il devient parfois difficile de trouver l'ensemble d'entrées uniformément distribué pour un algorithme, dans ce cas, Notation Big-O est utilisé qui représente la limite supérieure asymptotique d'une fonction f.
Pour plus de détails, veuillez consulter : Conception et analyse d'algorithmes .