В аналіз алгоритмів , асимптотичні позначення використовуються для оцінки продуктивності алгоритму, в його найкращі та найгірші випадки . У цій статті розглядатимуться позначення Big – Theta, представлені грецькою літерою (Θ).
визначення: Нехай g і f — функція від множини натуральних чисел до самої себе. Функція f називається Θ(g), якщо існують константи c1, c2> 0 і натуральне число n0такий, що c1* g(n) ≤ f(n) ≤ c2* g(n) для всіх n ≥ n0
Математичне представлення:
Θ (g(n)) = {f(n): існують позитивні константи c1, c2і п0так, що 0 ≤ c1* g(n) ≤ f(n) ≤ c2* g(n) для всіх n ≥ n0}
Примітка: Θ(g) є множиною
Наведене вище визначення означає, що якщо f(n) є тета від g(n), то значення f(n) завжди знаходиться між c1 * g(n) і c2 * g(n) для великих значень n (n ≥ n0). Визначення тета також вимагає, щоб f(n) було невід’ємним для значень n, більших за n0.
розкосі дерева
Графічне представлення:
Графічне представлення
Простою мовою нотація Big – Theta(Θ) визначає асимптотичні межі (як верхню, так і нижню) для функції f(n) і забезпечує середню часову складність алгоритму.
Виконайте наведені нижче кроки, щоб знайти середню складність часу будь-якої програми:
- Розбийте програму на менші сегменти.
- Знайдіть усі типи та кількість вхідних даних і обчисліть кількість операцій, які вони виконують. Переконайтеся, що регістри введення розподілені однаково.
- Знайдіть суму всіх обчислених значень і розділіть суму на загальну кількість вхідних даних, скажімо, отримана функція n дорівнює g(n) після видалення всіх констант, тоді в нотації Θ вона представлена як Θ(g(n))
приклад: Розглянемо приклад до визначити, чи існує ключ у масиві, за допомогою лінійного пошуку . Ідея полягає в тому, щоб перетнути масив і перевірити кожен елемент, чи дорівнює він ключу чи ні.
віл проти бика
Псевдокод виглядає наступним чином:
bool linearSearch(int a[], int n, int key) { for (int i = 0; i if (a[i] == key) return true; } return false; }>Нижче наведено реалізацію вищезазначеного підходу:
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> |
>
>
Вихід
Element is present in array>
Часова складність: O(n)
Допоміжний простір: О(1)
У задачі лінійного пошуку припустимо, що всі випадки є рівномірно розподілені (включаючи випадок відсутності ключа в масиві). Отже, підсумуйте всі випадки (коли ключ присутній у позиції 1, 2, 3, ……, n і відсутній, і розділіть суму на n + 1.
Середня складність розгляду справи =
⇒
⇒
⇒
(константи видалено)
каджал аггарвал
Коли використовувати позначення Big – Θ: Big – Θ аналізує алгоритм із найточнішою точністю, оскільки під час обчислення Big – Θ враховується рівномірний розподіл різних типів і довжин входів, він забезпечує середню часову складність алгоритму, яка є найбільш точною під час аналізу, однак на практиці іноді стає важко знайти рівномірно розподілений набір вхідних даних для алгоритму, у такому випадку, Позначення великого літери використовується, що представляє асимптотичну верхню межу функції f.
Щоб дізнатися більше, зверніться до: Проектування та аналіз алгоритмів .