ANALYSE AF ALGORITMER | BIG - Θ (BIG THETA) NOTATION - TECHCODEVIEW.COM

I den analyse af algoritmer , bruges asymptotiske notationer til at evaluere ydeevnen af en algoritme i dens bedste tilfælde og værste tilfælde . Denne artikel vil diskutere Big - Theta-notationer repræsenteret af et græsk bogstav (Θ).

Definition: Lad g og f være funktionen fra mængden af naturlige tal til sig selv. Funktionen f siges at være Θ(g), hvis der er konstanter c₁, c₂> 0 og et naturligt tal n₀sådan at c₁* g(n) ≤ f(n) ≤ c₂* g(n) for alle n ≥ n₀

Matematisk fremstilling:

Θ (g(n)) = {f(n): der findes positive konstanter c₁, c₂og n₀sådan at 0 ≤ c₁* g(n) ≤ f(n) ≤ c₂* g(n) for alle n ≥ n₀}
Bemærk: Θ(g) er et sæt

Ovenstående definition betyder, at hvis f(n) er theta af g(n), så er værdien f(n) altid mellem c1 * g(n) og c2 * g(n) for store værdier af n (n ≥ n)₀). Definitionen af theta kræver også, at f(n) skal være ikke-negativ for værdier på n større end n₀.

if-else sætning java

Grafisk fremstilling:

Grafisk fremstilling

I et simpelt sprog angiver Big – Theta(Θ) notation asymptotiske grænser (både øvre og nedre) for en funktion f(n) og giver den gennemsnitlige tidskompleksitet for en algoritme.

Følg nedenstående trin for at finde den gennemsnitlige tidskompleksitet for ethvert program:

Del programmet op i mindre segmenter.
Find alle typer og antal input, og beregn antallet af operationer, de tager for at blive udført. Sørg for, at input-sagerne er ligeligt fordelt.
Find summen af alle de beregnede værdier og divider summen med det samlede antal input lad os sige, at funktionen af n opnået er g(n) efter at have fjernet alle konstanterne, så i Θ-notation repræsenteret den som Θ(g(n))

Eksempel: Overvej et eksempel til finde ud af, om der findes en nøgle i et array eller ej ved hjælp af lineær søgning . Tanken er at krydse arrayet og kontroller hvert element, om det er lig med nøglen eller ej.

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 af ovenstående tilgang:

tilfældigt tal mellem 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>

Produktion

Element is present in array>

Tidskompleksitet: På)
Hjælpeplads: O(1)

I et lineært søgeproblem, lad os antage, at alle sagerne er ensartet fordelt (inklusive tilfældet, hvor nøglen er fraværende i arrayet). Så sum alle tilfældene (når nøglen er til stede i position 1, 2, 3, ……, n og ikke til stede, og divider summen med n + 1.

tcp og ip model

Gennemsnitlig sagstidskompleksitet = $frac{sum_{i=1}^{n+1} heta(i)}{n + 1}$

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

⇒

⇒ (konstanter fjernes)

Hvornår skal du bruge Big – Θ notation: Big – Θ analyserer en algoritme med den mest præcise nøjagtighed, da der ved beregning af Big – Θ tages hensyn til en ensartet fordeling af forskellige typer og længder af input, den giver den gennemsnitlige tidskompleksitet af en algoritme, som er mest præcis under analyse, men i praksis nogle gange bliver det svært at finde det ensartet fordelte sæt af input til en algoritme, i så fald, Big-O notation bruges som repræsenterer den asymptotiske øvre grænse for en funktion f.

For flere detaljer, se venligst: Design og analyse af algoritmer .

TechCodeview

Analyse af algoritmer | Stor – Θ (Big Theta) notation

C++

Java

Python3

C#

Javascript