logo

TechCodeview

Analyse von Algorithmen | Groß – Θ (Big Theta) Notation

Im Analyse von Algorithmen , asymptotische Notationen werden verwendet, um die Leistung eines Algorithmus zu bewerten Best Cases und Worst Cases . In diesem Artikel werden Big-Theta-Notationen erläutert, die durch einen griechischen Buchstaben (Θ) dargestellt werden.

Definition: Seien g und f die Funktion von der Menge der natürlichen Zahlen zu sich selbst. Die Funktion f heißt Θ(g), wenn es Konstanten c gibt1, C2> 0 und eine natürliche Zahl n0so dass c1* g(n) ≤ f(n) ≤ c2* g(n) für alle n ≥ n0

Mathematische Darstellung:



Θ (g(n)) = {f(n): Es existieren positive Konstanten c1, C2und n0so dass 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) für alle n ≥ n0}
Hinweis: Θ(g) ist eine Menge

Die obige Definition bedeutet, dass, wenn f(n) das Theta von g(n) ist, der Wert f(n) für große Werte von n (n ≥ n) immer zwischen c1 * g(n) und c2 * g(n) liegt0). Die Definition von Theta erfordert außerdem, dass f(n) für Werte von n größer als n nicht negativ sein darf0.

Leistungstest

Grafische Darstellung:

Grafische Darstellung

Vereinfacht ausgedrückt spezifiziert die Big-Theta(Θ)-Notation asymptotische Grenzen (sowohl obere als auch untere) für eine Funktion f(n) und liefert die durchschnittliche Zeitkomplexität eines Algorithmus.

Vor- und Nachteile der Technologie

Führen Sie die folgenden Schritte aus, um die durchschnittliche Zeitkomplexität eines Programms zu ermitteln:

  1. Teilen Sie das Programm in kleinere Abschnitte auf.
  2. Finden Sie alle Arten und Anzahlen von Eingaben und berechnen Sie die Anzahl der auszuführenden Operationen. Stellen Sie sicher, dass die Eingabefälle gleichmäßig verteilt sind.
  3. Finden Sie die Summe aller berechneten Werte und dividieren Sie die Summe durch die Gesamtzahl der Eingaben. Nehmen wir an, die erhaltene Funktion von n ist g(n), nachdem alle Konstanten entfernt wurden. In der Θ-Notation wird sie dann als Θ(g(n)) dargestellt.

Beispiel: Betrachten Sie ein Beispiel dazu Finden Sie mithilfe der linearen Suche heraus, ob ein Schlüssel in einem Array vorhanden ist oder nicht . Die Idee ist Durchqueren Sie das Array und prüfen Sie jedes Element, ob es dem Schlüssel entspricht oder nicht.

Der Pseudocode lautet wie folgt:

bool linearSearch(int a[], int n, int key) {  for (int i = 0; i   if (a[i] == key)  return true;  }   return false; }>

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

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>
>
>

Ausgabe 
Element is present in array>

Zeitkomplexität: An)
Hilfsraum: O(1)

Nehmen wir bei einem linearen Suchproblem an, dass alle Fälle zutreffen gleichmäßig verteilt (einschließlich des Falles, wenn der Schlüssel im Array fehlt). Summieren Sie also alle Fälle (wenn der Schlüssel an Position 1, 2, 3, ……, n vorhanden und nicht vorhanden ist) und dividieren Sie die Summe durch n + 1.

Durchschnittliche Fallzeitkomplexität = frac{sum_{i=1}^{n+1} heta(i)}{n + 1}

⇒ frac{ heta((n+1)*(n+2)/2)}{n+1}

Gitterstruktur

⇒ heta(1 + n/2)

⇒ heta(n)(Konstanten werden entfernt)

Wann sollte die Big-Θ-Notation verwendet werden: Big – Θ analysiert einen Algorithmus mit höchster Genauigkeit, da bei der Berechnung von Big – Θ eine gleichmäßige Verteilung verschiedener Arten und Längen von Eingaben berücksichtigt wird. Es liefert die durchschnittliche zeitliche Komplexität eines Algorithmus, der bei der Analyse, jedoch in der Praxis, am genauesten ist Manchmal wird es schwierig, den gleichmäßig verteilten Satz von Eingaben für einen Algorithmus zu finden. In diesem Fall gilt: Big-O-Notation verwendet, die die asymptotische Obergrenze einer Funktion f darstellen.

Weitere Einzelheiten finden Sie unter: Design und Analyse von Algorithmen .