Big-oh vs big-theta

Big-oh vs big-theta [중복]

---

가능성 :
Θ (n)과 O (n)의 차이점은 무엇입니까?

사람들이 알고리즘에 대해 이야기하는 것에 대해 비공식적으로 이야기 할 때, 그들이 빅오에 대해 이야기하는 것처럼 이야기합니다. 그러나 가끔씩 빅 세타를 자주 봅니다. 저는 수학적으로 둘 사이의 차이점을 알고 있습니다. 그러나 영어에서는 어떤 상황에서 big-theta be를 의미 할 때 big-oh를 사용할 것입니다. 부정확하거나 그 반대의 경우 (예제 알고리즘을 주시면 감사하겠습니다)?

보너스 : 사람들이 비공식적으로 말할 때 항상 big-oh를 사용하는 이유는 무엇입니까?

---

Big-O는 상한선입니다.

Big-Theta는 타이트 바운드, 즉 상한 및 하한입니다.

사람들이 상황에 처할 수있는 최악의 상황에 걱정할 때 큰 상황이 발생합니다. 즉, "이보다 훨씬 더 나빠질 수 없습니다"라고 말해요. 물론 경계가 좁을수록 더 좋지만, 경계가 항상 계산하기 쉬운 것은 아닙니다.

또한 사진

• Wikipedia / Big O 표기법

관련 질문

• Θ (n)과 O (n)의 차이점은 무엇입니까?

---

Wikipedia의 다음 인용문은 또한 약간의 빛을 비라도 다.

비공식적으로, 특히 컴퓨터 과학에서 Big O 표기법은 주어진 상황에서 Big Theta 표기법을 사용하는 것이 사실적으로 더 분명한 수있는 점근 타이트 바운드를 설명하기 위해 다소 남용되는 경우가 있습니다.

예를 들어, 함수 T(n) = 73n³ + 22n^(2)를 고려할 때 + 58다음의 모든 것이 일반적으로 허용되지만 일반적으로 바운드의 조임 (즉, 아래의 총알 2 및 3)이 바운드의 느슨 함 (즉, 아래의 총알 1)보다 강력하게 선호 됩니다.

1. T(n) = O(n¹⁰⁰) 과 동일하다, T(n) ∈ O(n⁽¹⁰⁰⁾)
2. T(n) = O(n⁽³⁾) 와 동일하다, T(n) ∈ O(n⁽³⁾)
3. T(n) = Θ(n⁽³⁾) 와 동일하다, T(n) ∈ Θ(n⁽³⁾)

동등한 영어 문장은 각각 다음과 가변합니다.

1. T(n)점근 적으로 ¹⁰⁰ 보다 빠르게 성장하지
   n
2. T(n)점근 적으로 ³ 보다 빠르게 성장하지n
3. T(n)n³ 만큼 빠르게 점근 적으로 증가합니다 .

사실 세 가지가 모두 사실이지만 더 많은 정보가 있습니다. 그러나 일부에서는에서는 Big Theta 표기법 (위 목록에서 글 머리 기호 번호 3)보다 Big O 표기법 (위 목록에서 글 머리 기호 번호 3)보다 일반적으로 사용됩니다. 더 느리게 성장하는 함수가 더 이상하기 때문입니다.

---

저는 수학자이고 알고리즘의 다수보고 필요하고 big-O, big-Theta 및 big-Omega 표기법을 여러 번보고 필요했습니다. 사람들이 말했듯이 빅 세타는 양면 경계입니다. 엄밀히 말해서 알고리즘이 얼마나 잘 할 수 있는지, 그 알고리즘이 더 잘할 수 있다는 것을 설명하고 싶을 때 더 잘할 수 있습니다. 예를 들어 "정렬에는 최악의 입력에 대해 Θ (n (log n)) 비교가 필요합니다"말하면 모든 입력에 대해 O (n (log n)) 비교를 사용하는 알고리즘이 있음을 설명합니다. ; 모든 정렬 알고리즘에 대해 Ω (n (log n)) 비교를 수행하도록 입력합니다.

이제 사람들이 Ω 대신 O를 사용하는 한 가지 좁은 이유는 최악 또는 평균 사례에 대한 면책 ​​조항을 삭제하는 것입니다. "정렬에는 O (n (log n)) 비교가 필요합니다."라고 말하면이 명령문은 여전히 ​​참입니다. 또 다른 좁은 이유는 X를 수행하는 하나의 알고리즘이 시간 Θ (f (n))이 걸리고 다른 알고리즘이 더 잘 수행 할 수 있으므로 X 자체의 적절한 것은 O (f (n)) 라고만 말할 수 있습니다 것 입니다.

그러나 사람들이 비공식적으로 O를 사용하는 더 넓은 이유가 있습니다. "명백"할 때 항상 "명백"할 때 나는 수학자이기 때문에 이상적으로는 "나는 비가 오면 우산을 가져갈 것입니다."또는 "나는 4 개의 공을 저글링 할 수 있습니다."라고 말하는 것이 있습니다. 레인즈 "또는"나는 "네 공을 저글링 수 있습니다. 그러나 그러한 진술의 나머지 절반은 종종 분명히 의도되거나 의도되지 않았습니다 . 명백한 것에 대해 엉성한 것은 인간의 본성 입니다 . 머리카락을 나누는 것이 혼란 스럽습니다.

불행히도 수학이나 알고리즘 이론과 같은 엄격한 영역에서 머리카락을 나누지 않는 것도 혼란 스럽습니다. 사람들은 Ω 또는 Θ라고 말해야 할 때 필연적으로 O라고 말할 것입니다. "명백하기"때문에 세부 사항을 건너 뛰는 것은 항상 오해로 이어집니다. 대한 해결책은 없습니다.

---

내 키보드에는 O 키가 있기 때문입니다.
Θ 또는 Ω 키가 없습니다.

나는 대부분의 사람들이 사용하게 게으르고 Θ를 의미 할 때 O를 사용한다고 생각합니다. 입력하기가 더 쉽기 때문입니다.

---

big O가 많이 사용되는 이유 중 하나는 너무 많이 사용되기 때문입니다. 많은 사람들이 표기법을보고 그것이 의미하는 바를 알고 있다고 생각한 다음 스스로 (잘못) 사용합니다. 이 공식 교육을받은 프로그래머들에게서 많이 발생합니다. 저도 한때 유죄였습니다.

또 다른 이유는 큰 세타보다 그리스어가 대부분의 키보드에서 큰 O를 입력하는 것이 더 쉽기 때문입니다.

그러나 나는 많은 것이 오류라고 생각합니다. 나는 방어 관련 프로그래밍에서 잠시 일하고 있다고 알리고 알고리즘 분석에 대해 거의 알지 있습니다. 이 시나리오에서 최악의 경우 성능은 항상 사람들이 관심을 갖고있는 것입니다. 최악의 경우 오류 시간에 보관 수 있기 때문입니다. 일어날 확률이 예를 들어 선박 승무원의 모든 구성원이 동시에 갑작스런 플루크 심장 마비를 배치 할 확률보다 낮은 것이 중요하지 않습니다 . 그래도 보관 수 있습니다.

물론 많은 알고리즘이 매우 일반적인 상황에서 최악의 경우를 가지고 있지만, 고전적인 예는 효과적으로 단일 연결 목록을 얻기 위해 이진 트리에 순서대로 삽입하는 것입니다. 평균 성능에 대한 "실제"평가는 서로 다른 종류의 입력에 대한 상대적 빈도를 고려해야합니다.

---

보너스 : 사람들이 비공식적으로 말할 때 항상 big-oh를 사용하는 이유는 무엇입니까?

big-oh에서이 루프는 :

for i = 1 to n do
    something in O(1) that doesn't change n and i and isn't a jump

입니다 O(n), O(n^2), O(n^3), O(n^1423424). big-oh는 상한 일 뿐이므로 타이트 바운드를 찾을 필요가 없기 때문에 계산하기가 더 쉽습니다.

그러나 위의 루프는 유일한 것 big-theta(n) 입니다.

에라토스테네스 체의 복잡성은 무엇입니까 ? O(n log n)당신이 틀리지 않겠다고 말 했지만, 그것도 최선의 대답이 아닐 것입니다. 라고 말하면 big-theta(n log n)틀렸을 것입니다.

---

가장 좋은 경우가 빠른 알고리즘이 있기 때문에 기술적으로 큰 Theta가 아니라 큰 O입니다.

Big O는 상한 이고 Big Theta는 등가 관계 입니다.

---

여기에는 좋은 답변이 많이 있지만 뭔가 빠진 것을 발견했습니다. 대부분의 답변은 사람들이 Big Theta보다 Big O를 사용하는 이유가 어려움 문제라는 것을 암시하는 것으로 보이며 어떤 경우에는 이것이 사실 일 수 있습니다. 종종 Big Theta 결과로 이어지는 증명은 Big O로 이어지는 증명보다 훨씬 더 복잡합니다. 이것은 일반적으로 사실이지만, 저는 이것이 하나의 분석을 다른 분석보다 사용하는 것과 큰 관련이 있다고 생각하지 않습니다.

복잡성에 대해 이야기 할 때 우리는 많은 것을 말할 수 있습니다. Big O 시간 복잡성은 알고리즘이 상한 내에서 실행되도록 보장되는 것을 알려주는 것입니다. Big Omega는 훨씬 덜 자주 논의되며 알고리즘이 실행되도록 보장되는 최소 시간 인 하한을 알려줍니다. 이제 Big Theta는이 두 숫자가 주어진 분석에서 실제로 동일하다고 말합니다. 이것은 응용 프로그램의 실행 시간이 매우 엄격하며 복잡성보다 점근 적으로 작은 값만큼만 벗어날 수 있음을 나타냅니다. 많은 알고리즘에는 점근 적으로 동일한 상한 및 하한이 없습니다.

따라서 Big Theta 대신 Big O를 사용하는 질문은 기술적으로 항상 유효하지만 Big O 대신 Big Theta를 사용하는 것은 Big O와 Big Omega가 동일한 경우에만 유효합니다. 예를 들어 삽입 정렬은 n ^ 2에서 Big О의 시간 복잡도를 갖지만 최상의 시나리오는 Big Omega를 n에 둡니다. 이 경우 시간 복잡도가 n 또는 n ^ 2의 Big Theta라고 말하는 것은 정확하지 않을 것입니다. 두 개의 다른 경계이고 그렇게 취급되어야하기 때문입니다.

---

나는 Big Theta를 보았고 학교에서 차이를 배웠다고 확신합니다. 그래도 찾아봐야 했어요. 이것은 Wikipedia가 말하는 것입니다.

Big O는 함수를 비교하는 데 가장 일반적으로 사용되는 점근 표기법이지만, 대부분의 경우 Big O는 점근 적으로 더 좁은 경계를 위해 Big Theta Θ로 대체 될 수 있습니다.

출처 : Big O Notation # 관련 점근 표기법

사람들이 공식적으로 말할 때 Big-O를 사용하는 이유를 모르겠습니다. 대부분의 사람들이 Big-Theta보다 Big-O에 더 익숙하기 때문일까요? 나는 당신이 나에게 상기시키기 전까지 Big-Theta가 존재한다는 것을 잊었다. 이제 기억이 새로워졌지만 결국 대화에 쓰게 될지도 모릅니다. :)

참고 URL : https://stackoverflow.com/questions/3230122/big-oh-vs-big-theta