Nel analisi degli algoritmi , le notazioni asintotiche vengono utilizzate per valutare le prestazioni di un algoritmo, nella sua casi migliori e casi peggiori . Questo articolo discuterà le notazioni Big – Theta rappresentate da una lettera greca (Θ).
Definizione: Siano g e f la funzione dall'insieme dei numeri naturali a se stessa. La funzione f si dice Θ(g), se esistono costanti c1, C2> 0 e un numero naturale n0tale che c1* g(n) ≤ f(n) ≤ c2* g(n) per ogni n ≥ n0
Rappresentazione matematica:
Θ (g(n)) = {f(n): esistono costanti positive c1, C2e n0tale che 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) per ogni n ≥ n0}
Nota: Θ(g) è un insieme
La definizione precedente significa che, se f(n) è theta di g(n), allora il valore f(n) è sempre compreso tra c1 * g(n) e c2 * g(n) per grandi valori di n (n ≥ n0). La definizione di theta richiede inoltre che f(n) debba essere non negativo per valori di n maggiori di n0.
modelli di apprendimento automatico
Rappresentazione grafica:
Rappresentazione grafica
In un linguaggio semplice, la notazione Big – Theta(Θ) specifica i limiti asintotici (sia superiori che inferiori) per una funzione f(n) e fornisce la complessità temporale media di un algoritmo.
Seguire i passaggi seguenti per trovare la complessità temporale media di qualsiasi programma:
- Suddividi il programma in segmenti più piccoli.
- Trova tutti i tipi e il numero di input e calcola il numero di operazioni necessarie per essere eseguite. Assicurarsi che i casi di input siano equamente distribuiti.
- Trova la somma di tutti i valori calcolati e dividi la somma per il numero totale di input, diciamo che la funzione di n ottenuta è g(n) dopo aver rimosso tutte le costanti, quindi nella notazione Θ è rappresentata come Θ(g(n))
Esempio: Considera un esempio trova se una chiave esiste in un array o meno utilizzando la ricerca lineare . L'idea è quella di attraversare la matrice e controlla ogni elemento se è uguale alla chiave o meno.
missione impossibile tutti i film
Lo pseudocodice è il seguente:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Di seguito è riportata l’implementazione dell’approccio di cui sopra:
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; }> |
>
>
Giava
// 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> |
>
>
Produzione
Element is present in array>
Complessità temporale: SU)
Spazio ausiliario: O(1)
In un problema di ricerca lineare, supponiamo che tutti i casi lo siano distribuito uniformemente (incluso il caso in cui la chiave è assente nell'array). Quindi, somma tutti i casi (quando la chiave è presente nella posizione 1, 2, 3, ……, n e non presente, e dividi la somma per n + 1.
Complessità temporale media del caso =
⇒
⇒
⇒
(le costanti vengono rimosse)
array di stringhe programmazione c
Quando utilizzare la notazione Big – Θ: Big – Θ analizza un algoritmo con la massima precisione poiché durante il calcolo di Big – Θ viene considerata una distribuzione uniforme di diversi tipi e lunghezze di input, fornisce la complessità temporale media di un algoritmo, che è più preciso durante l'analisi, tuttavia nella pratica a volte diventa difficile trovare l'insieme uniformemente distribuito di input per un algoritmo, in tal caso, Notazione O-grande viene utilizzato che rappresenta il limite superiore asintotico di una funzione f.
Per maggiori dettagli consultare: Progettazione e analisi di algoritmi .