In de analyse van algoritmen worden asymptotische notaties gebruikt om de prestaties van een algoritme te evalueren beste gevallen en slechtste gevallen . Dit artikel bespreekt Big-Theta-notaties, weergegeven door een Griekse letter (Θ).
Definitie: Laat g en f de functie zijn van de verzameling natuurlijke getallen naar zichzelf. De functie f heet Θ(g), als er constanten c zijn1, C2> 0 en een natuurlijk getal n0zodanig dat c1* g(n) ≤ f(n) ≤ c2* g(n) voor alle n ≥ n0
Wiskundige representatie:
Θ (g(n)) = {f(n): er bestaan positieve constanten c1, C2en N0zodanig dat 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) voor alle n ≥ n0}
Opmerking: Θ(g) is een verzameling
De bovenstaande definitie betekent dat als f(n) theta van g(n) is, de waarde f(n) altijd tussen c1 * g(n) en c2 * g(n) ligt voor grote waarden van n (n ≥ n0). De definitie van theta vereist ook dat f(n) niet-negatief moet zijn voor waarden van n groter dan n0.
hoe groot is deze monitor
Grafische weergave:
Grafische weergave
In eenvoudige taal specificeert de Big – Theta(Θ)-notatie asymptotische grenzen (zowel bovenste als onderste) voor een functie f(n) en geeft de gemiddelde tijdscomplexiteit van een algoritme weer.
c++ splitsreeks
Volg de onderstaande stappen om de gemiddelde tijdscomplexiteit van elk programma te vinden:
- Verdeel het programma in kleinere segmenten.
- Vind alle soorten en aantallen invoer en bereken het aantal bewerkingen dat nodig is om te worden uitgevoerd. Zorg ervoor dat de invoergevallen gelijk verdeeld zijn.
- Vind de som van alle berekende waarden en deel de som door het totale aantal invoer, laten we zeggen dat de verkregen functie van n g(n) is na het verwijderen van alle constanten, en vervolgens in Θ-notatie wordt weergegeven als Θ(g(n))
Voorbeeld: Denk eens aan een voorbeeld Ontdek of een sleutel in een array bestaat of niet met behulp van lineair zoeken . Het idee is om doorkruis de array en controleer elk element of het gelijk is aan de sleutel of niet.
De pseudocode is als volgt:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Hieronder vindt u de implementatie van de bovenstaande aanpak:
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> |
>
>
Uitvoer
Element is present in array>
Tijdcomplexiteit: Op)
Hulpruimte: O(1)
Laten we bij een lineair zoekprobleem aannemen dat alle gevallen dat zijn gelijk verdeeld (inclusief het geval waarin de sleutel afwezig is in de array). Tel dus alle gevallen bij elkaar op (als de sleutel aanwezig is op positie 1, 2, 3, ……, n en niet aanwezig, en deel de som door n + 1.
Gemiddelde complexiteit van de casustijd =
⇒
Python-padinstelling⇒
⇒
(constanten worden verwijderd)
Wanneer gebruik je de Big – Θ-notatie: Big – Θ analyseert een algoritme met de meest nauwkeurige nauwkeurigheid, omdat bij het berekenen van Big – Θ rekening wordt gehouden met een uniforme verdeling van verschillende soorten en lengtes van invoer. Het geeft de gemiddelde tijdscomplexiteit van een algoritme weer, die het meest nauwkeurig is tijdens het analyseren, maar in de praktijk soms wordt het moeilijk om de uniform verdeelde reeks invoergegevens voor een algoritme te vinden, in dat geval Big-O-notatie wordt gebruikt die de asymptotische bovengrens van een functie f vertegenwoordigt.
Voor meer details verwijzen wij u naar: Ontwerp en analyse van algoritmen .