Iekš algoritmu analīze , asimptotiskie apzīmējumi tiek izmantoti, lai novērtētu algoritma veiktspēju, tā labākie un sliktākie gadījumi . Šajā rakstā tiks apspriesti lielie un teta apzīmējumi, kas apzīmēti ar grieķu burtu (Θ).
Definīcija: Lai g un f ir funkcija no naturālo skaitļu kopas uz sevi. Funkciju f sauc par Θ(g), ja ir konstantes c1, c2> 0 un naturāls skaitlis n0tāds, ka c1* g(n) ≤ f(n) ≤ c2* g(n) visiem n ≥ n0
Matemātiskais attēlojums:
Θ (g(n)) = {f(n): pastāv pozitīvas konstantes c1, c2un n0tā, lai 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) visiem n ≥ n0}
Piezīme: Θ(g) ir kopa
Iepriekš minētā definīcija nozīmē, ja f(n) ir g(n) teta, tad vērtība f(n) vienmēr ir starp c1 * g(n) un c2 * g(n) lielām n vērtībām (n ≥ n).0). Teta definīcija arī nosaka, ka f(n) jābūt nenegatīvam, ja n ir lielāka par n.0.
virknes java masīvs
Grafiskais attēlojums:
Grafiskais attēlojums
Vienkāršā valodā Big – Theta(Θ) apzīmējums nosaka asimptotiskās robežas (gan augšējo, gan apakšējo) funkcijai f(n) un nodrošina algoritma vidējo sarežģītību laikā.
java iegūt pašreizējo laiku
Veiciet tālāk norādītās darbības, lai noskaidrotu jebkuras programmas vidējo laika sarežģītību.
- Sadaliet programmu mazākos segmentos.
- Atrodiet visus ievades veidus un skaitu un aprēķiniet to izpildei nepieciešamo darbību skaitu. Pārliecinieties, vai ievades gadījumi ir vienādi sadalīti.
- Atrodiet visu aprēķināto vērtību summu un izdaliet to ar kopējo ievades skaitu, pieņemsim, ka pēc visu konstantu noņemšanas iegūtā n funkcija ir g(n), tad Θ apzīmējumā tā tiek attēlota kā Θ(g(n))
Piemērs: Apsveriet piemēru izmantojot lineāro meklēšanu, noskaidrojiet, vai atslēga pastāv masīvā . Ideja ir šķērsot masīvu un pārbaudiet katru elementu, vai tas ir vienāds ar atslēgu.
Pseidokods ir šāds:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.
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> |
>
>
Izvade
Element is present in array>
Laika sarežģītība: O(n)
Palīgtelpa: O(1)
Lineārās meklēšanas uzdevumā pieņemsim, ka visi gadījumi ir vienmērīgi sadalīti (ieskaitot gadījumu, kad atslēgas masīvā nav). Tātad, summējiet visus gadījumus (kad atslēga atrodas pozīcijā 1, 2, 3, ……, n un neatrodas, un daliet summu ar n + 1.
Vidējā lietas laika sarežģītība =
⇒
python saraksta inicializācija⇒
⇒
(konstantes tiek noņemtas)
Kad lietot Big – Θ apzīmējumu: Big – Θ analizē algoritmu ar visprecīzāko precizitāti, jo, aprēķinot Big – Θ, tiek ņemts vērā dažāda veida un garuma ievades vienmērīgs sadalījums, tas nodrošina algoritma vidējo laika sarežģītību, kas ir visprecīzākā analīzes laikā, taču praksē dažreiz kļūst grūti atrast vienmērīgi sadalītu algoritma ievades kopu, tādā gadījumā Big-O apzīmējums tiek izmantots, kas attēlo funkcijas f asimptotisko augšējo robežu.
Lai iegūtu sīkāku informāciju, lūdzu, skatiet: Algoritmu projektēšana un analīze .