I den analys av algoritmer , används asymptotiska notationer för att utvärdera prestandan hos en algoritm, i dess bästa fall och värsta fall . Den här artikeln kommer att diskutera Big – Theta-noteringar som representeras av en grekisk bokstav (Θ).
Definition: Låt g och f vara funktionen från mängden naturliga tal till sig själv. Funktionen f sägs vara Θ(g), om det finns konstanter c1, c2> 0 och ett naturligt tal n0sådan att c1* g(n) ≤ f(n) ≤ c2* g(n) för alla n ≥ n0
Matematisk representation:
Θ (g(n)) = {f(n): det finns positiva konstanter c1, c2och n0så att 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) för alla n ≥ n0}
Obs: Θ(g) är en uppsättning
Ovanstående definition betyder att om f(n) är theta av g(n), så är värdet f(n) alltid mellan c1 * g(n) och c2 * g(n) för stora värden på n (n ≥ n)0). Definitionen av theta kräver också att f(n) måste vara icke-negativ för värden på n större än n0.
gimp spara som jpeg
Grafisk representation:
Grafisk representation
I ett enkelt språk anger Big – Theta(Θ) notation asymptotiska gränser (både övre och nedre) för en funktion f(n) och ger den genomsnittliga tidskomplexiteten för en algoritm.
Följ stegen nedan för att hitta den genomsnittliga tidskomplexiteten för ett program:
- Dela upp programmet i mindre segment.
- Hitta alla typer och antal ingångar och beräkna antalet operationer de tar för att utföras. Se till att ingångsfallen är jämnt fördelade.
- Hitta summan av alla beräknade värden och dividera summan med det totala antalet ingångar, låt säga att funktionen av n som erhålls är g(n) efter att ha tagit bort alla konstanter, sedan representeras den i Θ notation som Θ(g(n))
Exempel: Tänk på ett exempel hitta om en nyckel finns i en array eller inte med hjälp av linjär sökning . Tanken är att korsa arrayen och kontrollera varje element om det är lika med nyckeln eller inte.
Pseudokoden är som följer:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Nedan är implementeringen av ovanstående tillvägagångssätt:
linux byta namn på katalogen
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>
Tidskomplexitet: På)
Hjälputrymme: O(1)
I ett linjärt sökproblem, låt oss anta att alla fall är det jämnt utspridd (inklusive fallet när nyckeln saknas i arrayen). Så, summera alla fall (när nyckeln finns i position 1, 2, 3, ……, n och inte närvarande, och dividera summan med n + 1.
solig deol
Genomsnittlig falltidskomplexitet =
⇒
⇒
⇒
(konstanter tas bort)
När ska man använda Big – Θ notation: Big – Θ analyserar en algoritm med den mest exakta noggrannheten eftersom när man beräknar Big – Θ, beaktas en enhetlig fördelning av olika typer och längder av ingångar, den ger den genomsnittliga tidskomplexiteten för en algoritm, som är mest exakt vid analys, men i praktiken ibland blir det svårt att hitta den enhetligt fördelade uppsättningen av indata för en algoritm, i så fall, Big-O notation används som representerar den asymptotiska övre gränsen för en funktion f.
För mer information, se: Design och analys av algoritmer .