V analiza algoritmov , se asimptotični zapisi uporabljajo za ovrednotenje delovanja algoritma v njegovem najboljše in najslabše primere . Ta članek bo obravnaval oznake Big – Theta, ki jih predstavlja grška črka (Θ).
definicija: Naj bosta g in f funkcija iz množice naravnih števil sama sebi. Za funkcijo f pravimo, da je Θ(g), če obstajajo konstante c1, c2> 0 in naravno število n0tako da c1* g(n) ≤ f(n) ≤ c2* g(n) za vse n ≥ n0
Matematična predstavitev:
Θ (g(n)) = {f(n): obstajajo pozitivne konstante c1, c2in n0tako da je 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) za vse n ≥ n0}
Opomba: Θ(g) je množica
Zgornja definicija pomeni, da če je f(n) theta od g(n), potem je vrednost f(n) vedno med c1 * g(n) in c2 * g(n) za velike vrednosti n (n ≥ n0). Definicija theta prav tako zahteva, da mora biti f(n) nenegativen za vrednosti n, večje od n0.
js onload
Grafična predstavitev:
Grafična predstavitev
V preprostem jeziku zapis Big – Theta(Θ) podaja asimptotične meje (tako zgornje kot spodnje) za funkcijo f(n) in zagotavlja povprečno časovno kompleksnost algoritma.
Sledite spodnjim korakom, da ugotovite povprečno časovno zahtevnost katerega koli programa:
- Program razdelite na manjše segmente.
- Poiščite vse vrste in število vhodov ter izračunajte število operacij, ki jih je treba izvesti. Prepričajte se, da so primeri vnosa enakomerno porazdeljeni.
- Poiščite vsoto vseh izračunanih vrednosti in vsoto delite s skupnim številom vhodov, recimo, da je funkcija n, dobljena po odstranitvi vseh konstant, g(n), nato pa je v zapisu Θ predstavljena kot Θ(g(n))
primer: Razmislite o primeru z uporabo linearnega iskanja ugotovi, ali ključ obstaja v matriki ali ne . Ideja je, da prečkati niz in preverite vsak element, če je enak ključu ali ne.
sql vrstni red po datumu
Psevdokoda je naslednja:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Spodaj je izvedba zgornjega pristopa:
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> |
>
>
Izhod
Element is present in array>
Časovna zapletenost: O(n)
Pomožni prostor: O(1)
V problemu linearnega iskanja predpostavimo, da so vsi primeri enaki enakomerno porazdeljena (vključno s primerom, ko v matriki ni ključa). Torej seštejte vse primere (ko je ključ prisoten na mestu 1, 2, 3, ……, n in ni prisoten, in vsoto delite z n + 1.
Povprečna časovna zapletenost primera =
⇒
⇒
⇒
(konstante so odstranjene)
spanje v javascriptu
Kdaj uporabiti zapis Big – Θ: Big – Θ analizira algoritem z najnatančnejšo natančnostjo, saj se pri izračunu Big – Θ upošteva enakomerna porazdelitev različnih vrst in dolžin vhodov, zagotavlja povprečno časovno kompleksnost algoritma, ki je najbolj natančen pri analizi, vendar v praksi včasih postane težko najti enakomerno porazdeljen nabor vnosov za algoritem, v tem primeru Zapis z velikim O ki predstavljajo asimptotično zgornjo mejo funkcije f.
Za več podrobnosti glejte: Oblikovanje in analiza algoritmov .