ANALYSE AV ALGORITMER | STOR - Θ (BIG THETA) NOTASJON - TECHCODEVIEW.COM

I analyse av algoritmer , brukes asymptotiske notasjoner for å evaluere ytelsen til en algoritme, i dens beste tilfeller og verste tilfeller . Denne artikkelen vil diskutere Big – Theta-notasjoner representert med en gresk bokstav (Θ).

Definisjon: La g og f være funksjonen fra settet med naturlige tall til seg selv. Funksjonen f sies å være Θ(g), hvis det er konstanter c ₁ , c ₂ > 0 og et naturlig tall n ₀ slik at c ₁ * g(n) ≤ f(n) ≤ c ₂ * g(n) for alle n ≥ n ₀

Matematisk representasjon:

Θ (g(n)) = {f(n): det finnes positive konstanter c ₁ , c ₂ og n ₀ slik at 0 ≤ c ₁ * g(n) ≤ f(n) ≤ c ₂ * g(n) for alle n ≥ n ₀ }
Merk: Θ(g) er et sett

Definisjonen ovenfor betyr at hvis f(n) er theta av g(n), så er verdien f(n) alltid mellom c1 * g(n) og c2 * g(n) for store verdier av n (n ≥ n) ₀ ). Definisjonen av theta krever også at f(n) må være ikke-negativ for verdier på n større enn n ₀ .

Grafisk representasjon:

Grafisk representasjon

På enkelt språk spesifiserer Big – Theta(Θ)-notasjonen asymptotiske grenser (både øvre og nedre) for en funksjon f(n) og gir den gjennomsnittlige tidskompleksiteten til en algoritme.

Følg trinnene nedenfor for å finne den gjennomsnittlige tidskompleksiteten til ethvert program:

Del opp programmet i mindre segmenter.
Finn alle typer og antall innganger og beregn antall operasjoner de tar for å bli utført. Sørg for at innspillsakene er likt fordelt.
Finn summen av alle de beregnede verdiene og del summen med det totale antallet innganger, la oss si at funksjonen til n oppnådd er g(n) etter å ha fjernet alle konstantene, så i Θ-notasjon representeres den som Θ(g(n))

Eksempel: Tenk på et eksempel finne ut om en nøkkel finnes i en matrise eller ikke ved å bruke lineært søk . Tanken er å krysse matrisen og sjekk hvert element om det er lik nøkkelen eller ikke.

Pseudokoden er som følger:

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

Nedenfor er implementeringen av tilnærmingen ovenfor:

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>

Produksjon

Element is present in array

Tidskompleksitet: På)
Hjelpeplass: O(1)

I et lineært søkeproblem, la oss anta at alle tilfellene er det jevnt fordelt (inkludert tilfellet når nøkkelen er fraværende i arrayet). Så summerer alle tilfellene (når nøkkelen er tilstede i posisjon 1, 2, 3, ……, n og ikke til stede, og del summen med n + 1.

Gjennomsnittlig sakstidskompleksitet = $frac{sum_{i=1}^{n+1} heta(i)}{n + 1}$

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

⇒

⇒ (konstanter fjernes)

Når skal du bruke Big – Θ-notasjon: Big – Θ analyserer en algoritme med mest presis nøyaktighet siden mens man beregner Big – Θ, vurderes det en ensartet fordeling av forskjellige typer og lengder på innganger, den gir den gjennomsnittlige tidskompleksiteten til en algoritme, som er mest presis under analyse, men i praksis noen ganger blir det vanskelig å finne det jevnt fordelte settet med innganger for en algoritme, i så fall, Big-O-notasjon brukes som representerer den asymptotiske øvre grensen til en funksjon f.

For mer informasjon, vennligst se: Design og analyse av algoritmer .