logo

TechCodeview

Algoritmien analyysi | Big – Θ (Big Theta) -merkintä

Vuonna algoritmien analyysi , asymptoottisia merkintöjä käytetään arvioimaan algoritmin suorituskykyä sen parhaat ja huonot tapaukset . Tässä artikkelissa käsitellään Big – Theta -merkintöjä, joita edustaa kreikkalainen kirjain (Θ).

Määritelmä: Olkoot g ja f funktio luonnollisten lukujen joukosta itseensä. Funktion f sanotaan olevan Θ(g), jos on vakioita c1, c2> 0 ja luonnollinen luku n0sellainen, että c1* g(n) ≤ f(n) ≤ c2* g(n) kaikille n ≥ n0



Matemaattinen esitys:

Θ (g(n)) = {f(n): on olemassa positiivisia vakioita c1, c2ja n0siten, että 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) kaikille n ≥ n0}
Huomautus: Θ(g) on ​​joukko

Yllä oleva määritelmä tarkoittaa, että jos f(n) on g(n) theta, niin arvo f(n) on aina välillä c1 * g(n) ja c2 * g(n) suurille n:n arvoille (n ≥ n).0). Thetan määritelmä edellyttää myös, että f(n):n on oltava ei-negatiivinen, jos n on suurempi kuin n0.



amisha patel

Graafinen esitys:

Graafinen esitys

Yksinkertaisella kielellä Big – Theta(Θ) -merkintä määrittää asymptoottiset rajat (sekä ylä- että alarajat) funktiolle f(n) ja antaa algoritmin keskimääräisen aikamonimutkaisuuden.



Seuraa alla olevia ohjeita löytääksesi minkä tahansa ohjelman keskimääräinen aika monimutkaisuus:

  1. Jaa ohjelma pienempiin osiin.
  2. Etsi kaikki syötteiden tyypit ja määrä ja laske niiden suorittamiseen tarvittavien toimintojen määrä. Varmista, että syöttötapaukset jakautuvat tasaisesti.
  3. Etsi kaikkien laskettujen arvojen summa ja jaa summa syötteiden kokonaismäärällä. Sanotaan, että saatu n:n funktio on g(n) kaikkien vakioiden poistamisen jälkeen, sitten Θ-merkinnällä se esitetään muodossa Θ(g(n))

Esimerkki: Harkitse esimerkkiä selvittää, onko avain taulukossa vai ei, käyttämällä lineaarihakua . Ideana on kulkea taulukon läpi ja tarkista jokainen elementti, onko se yhtä suuri kuin avain vai ei.

kokonaisluku double java

Pseudokoodi on seuraava:

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

Alla on yllä olevan lähestymistavan toteutus:

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

Python 3

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

Lähtö 
Element is present in array>

Aika monimutkaisuus: Päällä)
Aputila: O(1)

Lineaarisessa hakutehtävässä oletetaan, että kaikki tapaukset ovat tasaisesti jakautunut (mukaan lukien tapaus, jossa avain puuttuu taulukosta). Joten summaa kaikki tapaukset (kun avain on paikalla 1, 2, 3, ……, n ja ei ole läsnä, ja jaa summa n + 1:llä.

Keskimääräinen tapauksen aika monimutkaisuus = 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)(vakiot poistetaan)

bash lukea tiedosto

Milloin käyttää Big – Θ-merkintää: Big – Θ analysoi algoritmin tarkimmalla tarkkuudella, koska Big – Θ:tä laskettaessa otetaan huomioon erityyppisten ja pituisten syötteiden tasainen jakautuminen, se antaa algoritmin keskimääräisen aikamonimutkaisuuden, joka on tarkin analysoitaessa, mutta käytännössä joskus on vaikea löytää tasaisesti jakautunutta syötejoukkoa algoritmille, siinä tapauksessa Big-O-merkintä käytetään, joka edustaa funktion f asymptoottista ylärajaa.

Katso lisätietoja: Algoritmien suunnittelu ja analyysi .