Viduje algoritmų analizė , asimptotiniai žymėjimai naudojami algoritmo veikimui įvertinti, jo geriausiais ir blogiausiais atvejais . Šiame straipsnyje bus aptariami dideli – teta žymėjimai, pavaizduoti graikiška raide (Θ).
Apibrėžimas: Tegul g ir f yra funkcija nuo natūraliųjų skaičių aibės iki savęs. Sakoma, kad funkcija f yra Θ(g), jei yra konstantų c1, c2> 0 ir natūralusis skaičius n0toks, kad c1* g(n) ≤ f(n) ≤ c2* g(n) visiems n ≥ n0
Matematinis vaizdavimas:
Θ (g(n)) = {f(n): yra teigiamų konstantų c1, c2ir n0taip, kad 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) visiems n ≥ n0}
Pastaba: Θ(g) yra aibė
Aukščiau pateiktas apibrėžimas reiškia, kad jei f(n) yra g(n) teta, tada reikšmė f(n) visada yra tarp c1 * g(n) ir c2 * g(n), esant didelėms n reikšmėms (n ≥ n).0). Teta apibrėžimas taip pat reikalauja, kad f(n) būtų neneigiamas, kai n reikšmės yra didesnės nei n0.
np std
Grafinis vaizdavimas:
Grafinis vaizdavimas
Paprasta kalba Big – Theta(Θ) žymėjimas nurodo funkcijos f(n) asimptotines ribas (ir viršutinę, ir apatinę) ir pateikia vidutinį algoritmo sudėtingumą laike.
Atlikite toliau nurodytus veiksmus, kad sužinotumėte vidutinį bet kurios programos laiko sudėtingumą:
- Padalinkite programą į mažesnius segmentus.
- Raskite visų tipų įvesčių skaičių ir skaičių bei apskaičiuokite operacijų, kurių reikia, kad jos būtų įvykdytos. Įsitikinkite, kad įvesties atvejai yra vienodai paskirstyti.
- Raskite visų apskaičiuotų reikšmių sumą ir padalykite ją iš bendro įėjimų skaičiaus, tarkime, kad n funkcija gauta g(n), pašalinus visas konstantas, tada Θ žymėjime ji pavaizduota kaip Θ(g(n))
Pavyzdys: Apsvarstykite pavyzdį Naudodami tiesinę paiešką sužinokite, ar masyve yra raktas, ar ne . Idėja yra pereiti masyvą ir patikrinkite kiekvieną elementą, ar jis lygus raktui, ar ne.
Pseudokodas yra toks:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Žemiau pateikiamas pirmiau minėto metodo įgyvendinimas:
kas yra prologas
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> |
>
>
Išvestis
Element is present in array>
Laiko sudėtingumas: O(n)
Pagalbinė erdvė: O(1)
Tiesinės paieškos užduotyje tarkime, kad visi atvejai yra tolygiai paskirstytas (įskaitant atvejį, kai masyve nėra rakto). Taigi, susumuokite visus atvejus (kai raktas yra 1, 2, 3, ……, n padėtyse ir jo nėra, ir padalykite sumą iš n + 1.
css teksto lygiavimas
Vidutinis bylos sudėtingumas =
⇒
⇒
⇒
(konstantos pašalinamos)
Kada naudoti Big – Θ žymėjimą: Big – Θ tiksliausiu tikslumu analizuoja algoritmą, kadangi skaičiuojant Big – Θ atsižvelgiama į vienodą įvairaus tipo ir ilgio įėjimų pasiskirstymą, jis pateikia vidutinį algoritmo sudėtingumą laike, kuris yra tiksliausias analizuojant, tačiau praktiškai. kartais tampa sunku rasti tolygiai paskirstytą algoritmo įvesties rinkinį, tokiu atveju Big-O žymėjimas naudojamas, kuris reiškia asimptotinę viršutinę funkcijos f ribą.
Norėdami gauti daugiau informacijos, žr. Algoritmų projektavimas ir analizė .