하한과 단단한 경계의 차이점은 무엇입니까?

Question

이것의 참조로 대답, theta (tight bound) 란 무엇입니까?

오메가는 알고리즘이 수행 할 수있는 최소 시간을 낮추고 이해합니다. 그리고 우리는 Big-O가 상한을위한 것임을 알고 있으며, 알고리즘이 취할 수있는 최대 시간을 의미합니다. 그러나 나는 세타에 대해 전혀 모른다.

Answer 1

큰 o 상한입니다 오메가 하부입니다. 세타 Big O와 Omega가 모두 필요하므로 그것이 단단한 바운드 (상단과 하한이어야합니다).

예를 들어, 알고리즘을 가져옵니다 Omega(n log n) 적어도 취합니다 n log n 시간이지만 상한은 없습니다. 알고리즘 복용 Theta(n log n) 걸리기 때문에 우선적입니다 적어도 n log n (오메가 n 로그 N) 및 더 이상 n log n (큰 o n log n).

Answer 2

θ- 계약 (theta 표기법)은 더 정확하기 때문에 단단한 바운드라고합니다. o- 노트 그리고 ω- 통치 (오메가 표기법).

내가 게으른 경우, 정렬 된 배열에서 이진 검색이 O (n이라고 말할 수 있습니다.²), 에³) 및 O (2^N), 그리고 나는 모든 경우에 기술적으로 정확할 것입니다. O- Notation은 단지 an을 지정하기 때문입니다 상한, 및 바이너리 검색은 이러한 모든 기능에 의해 높은 측면에 묶여 있습니다. 이러한 게으른 추정치는 될 것입니다 쓸모없는.

θ- 계약은이 문제를 해결합니다 결합 O- 노트 및 ω- 통과. 이진 검색이 θ (log n)라고 말하면 더 정확한 정보를 제공합니다. 알고리즘이 묶여 있음을 알려줍니다 둘 다 주어진 함수에 의한 측면이므로 명시된 것보다 훨씬 빠르거나 느리지 않습니다.

Answer 3

당신이 뭔가가 있다면 O (F (N)) 그것은 있다는 것을 의미합니다 케이, G (N) 그렇게 f (n) ≤ kg (n).

당신이 뭔가가 있다면 ω (F (N)) 그것은 있다는 것을 의미합니다 케이, G (N) 그렇게 f (n) ≥ kg (n).

그리고 당신이 뭔가가 있다면 O (F (N)) 그리고 ω (F (N)), 그럼입니다 θ (f (n).

그만큼 위키 백과 기사 약간 밀도가 높으면 괜찮습니다.

Answer 4

점근 적 상한 주어진 알고리즘이 입력 수에 따라 최대 시간 동안 실행됨을 의미합니다.

정렬 알고리즘을 예로 들어 봅시다. 배열의 모든 요소가 내림차순 순서라면 정렬하려면 실행 시간이 걸립니다. O(n), 상한 복잡성을 보여줍니다. 배열이 이미 정렬 된 경우 값은 O(1).

일반적으로, O-notation 상한 복잡성에 사용됩니다.

---

비대칭 적으로 단단한 바운드 (씨₁g (n) ≤ f (n) ≤ c₂g (n))은 함수에 대한 평균 결합 복잡성을 보여줍니다.₁ 그리고 c₂ 상수입니다.

Answer 5

문구 최소 시간 그리고 최대 시간 여기서 약간 오해의 소지가 있습니다. 우리가 큰 O 표기법에 대해 이야기 할 때, 우리가 관심있는 실제 시간이 아니며, 입력 크기가 커질 때 시간이 증가하는 방법입니다. 그리고 그것은 보통 우리가 말하는 평균 또는 최악의 시간입니다. 가장 좋습니다, 일반적으로 우리의 문제를 해결하는 데 의미가 없습니다.

다른 질문에 대한 허용 된 답변에서 배열 검색을 사용합니다. 크기 n 목록에서 특정 숫자를 찾는 데 걸리는 시간은 평균적으로 n/2 * some_constant입니다. 기능으로 취급하는 경우 f(n) = n/2*some_constant, 그것은 더 빨리 증가하지 않습니다 g(n) = n, 찰리가주는 의미에서. 또한, 그것은 느리게 증가하지 않습니다 g(n) 어느 하나. 따라서, g(n) 실제로 상한과 하한입니다. f(n) Big-O 표기법에서는 선형 검색의 복잡성이 바로 그거죠 N, 그것이 theta (n)임을 의미합니다.

이와 관련하여, 다른 질문에 대한 받아 들여진 답변에 대한 설명은 완전히 정확하지 않으며, 이는 일부 입력에 대해 알고리즘이 일정한 시간에 실행될 수 있기 때문에 O (n)은 상한이라고 주장합니다 (이것은 가장 좋습니다 위에서 언급했는데, 실제로 우리가 실행 시간에 대해 알고 싶은 것은 아닙니다).

Answer 6

게으른 경우 정렬 된 배열의 이진 검색이 O (N2), O (N3) 및 O (2N)이라고 말할 수 있으며 모든 경우에 기술적으로 정확합니다.

우리는 o- 반드시 ( "Little-OH")를 사용하여 비대칭 적으로 빡빡하지 않은 상한을 나타낼 수 있습니다. Big-Oh와 Little-Oh는 모두 비슷합니다. 그러나 Big-OH는 비대칭 적으로 단단한 상한을 정의하는 데 사용될 수 있습니다.

Answer 7

정확히 하한 또는 $ Omega $ bfon f (n)은 f (n)와 비대칭 적으로 또는 동일 한 함수 세트를` '일부 c, n'$ in $ $ bbb {n} $

그리고 f (n)의 상한 또는 $ mathit {o} $는 수학적으로 알려주는 f (n)과 같은 함수 세트를 의미합니다.

$ g (n) ge cf (n) 모든 n ge n '$에 대해, 일부 c, n'$ in $ $ bbb {n} $.

이제 $ theta $는 위의 쓰여진 두 가지의 교차점입니다.

$\theta $

알고리즘이 "정확히 $ omega left (f (n) right $"와 같으면 $ theta left (f (n) right) $라고 말하는 것이 좋습니다.

또는, 우리는 또한 우리에게 실제 속도를 준다고 말할 수 있습니다. $ \omega $ 우리에게 가장 낮은 한계를 제공합니다.

Answer 8

간의 기본 차이

블록 쿼트

비대칭 적으로 상한 및 비대칭 적으로 단단한 비대칭 .upperbound는 입력 수에 따라 최대 시간으로 실행할 수있는 주어진 algorythm을 의미합니다. 상한 복잡성을 나타내는 O (n)의 실행 시간이 걸리지 만 이미 정렬 된 경우 옴 (1)이 필요합니다. 따라서 우리는 일반적으로 상한 복잡성에 "O"표기법을 사용했습니다.

비대칭. Tightbound 경계는 for (c1g (n) <= f (n) <= c2g (n))을 보여줍니다. 함수가 두 바운드 (상한과 하부) 사이의 값을 갖도록 단단한 결합 한계를 보여줍니다. 평균 사례.