logo

TechCodeview

Analyse av algoritmer | Stor – Θ (Big Theta) notasjon

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 c1, c2> 0 og et naturlig tall n0slik at c1* g(n) ≤ f(n) ≤ c2* g(n) for alle n ≥ n0

Matematisk representasjon:



Θ (g(n)) = {f(n): det finnes positive konstanter c1, c2og n0slik at 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) for alle n ≥ n0}
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)0). Definisjonen av theta krever også at f(n) må være ikke-negativ for verdier på n større enn n0.

er proteinfett

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:

  1. Del opp programmet i mindre segmenter.
  2. Finn alle typer og antall innganger og beregn antall operasjoner de tar for å bli utført. Sørg for at innspillsakene er likt fordelt.
  3. 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:

tilfeldig tall mellom 1 og 10

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.

når starter q2

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

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

⇒ heta(1 + n/2)

⇒ heta(n)(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 .