În analiza algoritmilor , notațiile asimptotice sunt folosite pentru a evalua performanța unui algoritm, în sa cele mai bune cazuri și cele mai rele cazuri . Acest articol va discuta notațiile Big – Theta reprezentate printr-o literă grecească (Θ).
Definiție: Fie g și f funcția de la mulțimea numerelor naturale la sine. Funcția f se spune că este Θ(g), dacă există constante c1, c2> 0 și un număr natural n0astfel încât c1* g(n) ≤ f(n) ≤ c2* g(n) pentru toate n ≥ n0
Reprezentare matematică:
Θ (g(n)) = {f(n): există constante pozitive c1, c2si n0astfel încât 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) pentru toate n ≥ n0}
Notă: Θ(g) este o mulțime
Definiția de mai sus înseamnă că, dacă f(n) este teta lui g(n), atunci valoarea f(n) este întotdeauna între c1 * g(n) și c2 * g(n) pentru valori mari ale lui n (n ≥ n).0). Definiția lui theta necesită, de asemenea, ca f(n) să fie nenegativ pentru valorile lui n mai mari decât n0.
ce este uri
Reprezentare grafică:
Reprezentare grafică
Într-un limbaj simplu, notația Big – Theta(Θ) specifică limite asimptotice (atât superioare, cât și inferioare) pentru o funcție f(n) și oferă complexitatea timpului mediu a unui algoritm.
face scriptul executabil
Urmați pașii de mai jos pentru a găsi complexitatea timpului mediu a oricărui program:
- Împărțiți programul în segmente mai mici.
- Găsiți toate tipurile și numărul de intrări și calculați numărul de operațiuni necesare pentru a fi executate. Asigurați-vă că cazurile de intrare sunt distribuite egal.
- Aflați suma tuturor valorilor calculate și împărțiți suma la numărul total de intrări, să spunem că funcția lui n obținută este g(n) după îndepărtarea tuturor constantelor, apoi în notația Θ este reprezentată ca Θ(g(n))
Exemplu: Luați în considerare un exemplu pentru aflați dacă o cheie există într-o matrice sau nu folosind căutarea liniară . Ideea este să traversează matricea și verificați fiecare element dacă este egal cu cheia sau nu.
Pseudo-codul este următorul:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Mai jos este implementarea abordării de mai sus:
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> |
>
>
Ieșire
Element is present in array>
Complexitatea timpului: Pe)
Spațiu auxiliar: O(1)
Într-o problemă de căutare liniară, să presupunem că toate cazurile sunt distribuit uniform (inclusiv cazul în care cheia este absentă în matrice). Deci, însumați toate cazurile (când cheia este prezentă la poziția 1, 2, 3, ……, n și nu este prezentă și împărțiți suma la n + 1.
Complexitatea medie a timpului cazului =
⇒
care este 10 din 60⇒
⇒
(constantele sunt eliminate)
Când să folosiți notația Big – Θ: Big – Θ analizează un algoritm cu cea mai precisă acuratețe, deoarece în timpul calculului Big – Θ, se ia în considerare o distribuție uniformă a diferitelor tipuri și lungimi de intrări, acesta oferă complexitatea timpului mediu a unui algoritm, care este cel mai precis în timpul analizei, totuși în practică. uneori devine dificil să găsești setul uniform distribuit de intrări pentru un algoritm, în acest caz, Notație Big-O este folosită care reprezintă limita superioară asimptotică a unei funcții f.
Pentru mai multe detalii, vă rugăm să consultați: Proiectarea și analiza algoritmilor .