빅 세타 및 점근 표기법 설명

Big Omega는 함수 런타임의 하한을 알려주고 Big O는 상한을 알려줍니다.

종종 서로 다르며 런타임에 보장 할 수 없습니다. 두 경계와 입력간에 차이가 있습니다. 그러나 그들이 똑같 으면 어떻게 될까요? 그런 다음 세타 (Θ) 바운드를 제공 할 수 있습니다. 어떤 입력을 제공하든 함수는 해당 시간에 실행됩니다.

일반적으로 가장 정확하고 엄격한 경계이기 때문에 가능하면 항상 세타 경계를 지정하려고합니다. 세타 경계를 줄 수 없다면 다음으로 좋은 것은 가능한 한 가장 엄격한 O 경계입니다.

예를 들어 배열에서 값 0을 검색하는 함수를 사용합니다.

def containsZero(arr): #assume normal array of length n with no edge cases for num x in arr: if x == 0: return true return false
  1. 가장 좋은 경우는 무엇입니까? 음, 배열에 첫 번째 값이 0이면 일정한 시간이 걸립니다. Ω (1)
  2. 최악의 경우는 무엇입니까? 배열에 0이 없으면 전체 배열을 반복합니다. O (n)

우리는 그것에 오메가와 O 경계를 부여했습니다. 그래서 세타는 어떻습니까? 우리는 그것을 줄 수 없습니다! 우리가 제공하는 배열에 따라 런타임은 상수와 선형 사이에있을 것입니다.

코드를 약간 변경해 보겠습니다.

def printNums(arr): #assume normal array of length n with no edge cases for num x in arr: print(x)

최상의 경우와 최악의 경우를 생각할 수 있습니까 ?? 난 못해! 어떤 배열을 제공하더라도 배열의 모든 값을 반복해야합니다. 따라서이 함수는 최소한 n 시간 (Ω (n))이 걸리지 만 n 시간 (O (n))보다 오래 걸리지 않을 것입니다. 이것은 무엇을 의미 하는가? 함수는 정확히 n 시간 이 걸립니다 : Θ (n).

경계가 혼란 스러우면 이렇게 생각해보세요. 우리는 x와 y의 2 개의 숫자를 가지고 있습니다. x <= y 및 y <= x가 주어집니다. x가 y보다 작거나 같고 y가 x보다 작거나 같으면 x는 y와 같아야합니다!

연결 목록에 익숙하다면 자신을 테스트하고 이러한 각 기능의 런타임에 대해 생각해보십시오!

  1. 가져 오기
  2. 없애다
  3. 더하다

이중 연결 목록을 고려하면 상황이 더욱 흥미로워집니다!

점근 표기법

알고리즘의 성능 가치를 어떻게 측정합니까?

시간이 우리의 가장 귀중한 자원 중 하나임을 고려하십시오. 컴퓨팅에서는 프로세스가 완료되는 데 걸리는 시간으로 성능을 측정 할 수 있습니다. 두 알고리즘으로 처리 된 데이터가 동일하면 문제 해결을위한 최상의 구현을 결정할 수 있습니다.

알고리즘의 수학적 한계를 정의하여이를 수행합니다. 이것들은 big-O, big-omega, big-theta 또는 알고리즘의 점근 표기법입니다. 그래프에서 big-O는 주어진 데이터 세트 또는 "상한"에 대해 알고리즘이 걸릴 수있는 가장 긴 시간입니다. Big-omega는 "lower bound"인 big-O의 반대입니다. 여기에서 알고리즘이 모든 데이터 세트에 대해 최고 속도에 도달합니다. Big theta는 알고리즘의 정확한 성능 값이거나 좁은 상한과 하한 사이의 유용한 범위입니다.

몇 가지 예 :

  • "당신의 일생 안에 배달 될 것입니다." (big-O, 상한선)
  • “적어도 1 달러는 지불 할 수 있습니다.” (빅 오메가, 하한)
  • "오늘 최고 기온은 25ºC, 최저 기온은 19ºC입니다." (큰 세타, 좁은)
  • "해변까지 걸어서 1km입니다." (빅 세타, 정확함)

추가 정보:

//www.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/big-big-theta-notation //stackoverflow.com/questions/10376740/what-exactly-does-big-%D3% A8- 표기-대표 //www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/