알고리즘 분석 | BIG - Θ(BIG THETA) 표기법 - TECHCODEVIEW.COM

에서 알고리즘 분석 , 점근적 표기법은 알고리즘의 성능을 평가하는 데 사용됩니다. 최선의 경우와 최악의 경우 . 이 기사에서는 그리스 문자(Θ)로 표시되는 Big – Theta 표기법에 대해 설명합니다.

정의: g와 f를 자연수 집합 자체에 대한 함수로 둡니다. 상수 c가 있는 경우 함수 f는 Θ(g)라고 합니다. ₁ , 씨 ₂ > 0 및 자연수 n ₀ 그런 c ₁ * g(n) ≤ f(n) ≤ c ₂ * 모든 n ≥ n에 대한 g(n) ₀

수학적 표현:

Θ (g(n)) = {f(n): 양의 상수 c가 존재함 ₁ , 씨 ₂ 그리고 n ₀ 0 ≤ c가 되도록 ₁ * g(n) ≤ f(n) ≤ c ₂ * 모든 n ≥ n에 대한 g(n) ₀ }
참고: Θ(g)는 집합입니다.

위의 정의는 f(n)이 g(n)의 세타인 경우 값 f(n)은 n의 큰 값(n ≥ n)에 대해 항상 c1 * g(n)과 c2 * g(n) 사이에 있음을 의미합니다. ₀ ). 또한 세타의 정의에서는 f(n)이 n보다 큰 n 값에 대해 음수가 아니어야 함을 요구합니다. ₀ .

그래픽 표현:

그래픽 표현

간단한 언어에서 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 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>

파이썬3

# 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# 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 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

시간 복잡도: 에)
보조 공간: 오(1)

선형 탐색 문제에서 모든 경우가 다음과 같다고 가정해 보겠습니다. 균일하게 분포 (배열에 키가 없는 경우도 포함) 그래서 모든 경우(키가 1, 2, 3, …, n 위치에 존재하고 존재하지 않는 경우)를 모두 합산하고 그 합을 n + 1로 나눕니다.

평균 사례 시간 복잡도 = $frac{sum_{i=1}^{n+1} heta(i)}{n + 1}$

⇒ $frac{ heta((n+1)*(n+2)/2)}{n+1}$

⇒

⇒ (상수는 제거됩니다)

Big – Θ 표기법을 사용하는 경우: Big – Θ는 다양한 유형과 입력 길이의 균일한 분포인 Big – Θ를 계산하는 동안 알고리즘의 평균 시간 복잡도를 제공하므로 가장 정확한 정확도로 알고리즘을 분석하지만 실제로는 분석하는 동안 가장 정확합니다. 때로는 알고리즘에 대해 균일하게 분포된 입력 집합을 찾는 것이 어려워집니다. 이 경우 빅오 표기법 함수 f의 점근적 상한을 나타내는 데 사용됩니다.

자세한 내용은 다음을 참조하세요. 알고리즘 설계 및 분석 .