나는 수학적으로 $ f (n) \ in O (g (n)) $ : $ f (n) $는 이해하지 못합니다. $ g (n) $보다 빠르게 성장합니다. 좀 더 공식적으로 $ \ exists c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
마찬가지로 $ f (n) \ in \ Theta (g (n)) $는 $ f (n) $가 $ g (n) $만큼 빠르게 증가한다는 것을 의미합니다. ie $ f (n) \ in O (g (n)), \ Omega (g (n)) $.
내가 이해하지 못하는 것은 사람들이 실행 시간에 big Oh를 사용하는 이유입니다. 알고리즘? 빅 세타를 사용하면 안됩니다. 알고리즘의 “실행 시간”이라고 말하면 최악의 실행 시간 즉, $ T (n) = max \ {ALG (x) : | x | = n \} $.
예 : $ n $ ($ n $ 요소 및 대상 값) 크기 입력에 대한 선형 검색의 최악의 실행 시간은 $ \ Theta (n)입니다. $ 및 $ O (n) $,하지만 $ \ Theta (n) $는 더 많은 정보를 제공합니다. 따라서 알고리즘 북은 $ \ Theta (n) $가 아닌 $ O (n) $를 사용하는 이유입니다.
댓글
- 자주 사용 '는 알고리즘의 실행 시간에 대한 엄격한 빅 세타 경계를 ' 얻을 수 없기 때문입니다. 알고리즘이 충분히 복잡하다면 실행 시간이 $ O (n ^ {n!}) $라고 말할 수 있습니다. 실제로 $ \ Theta (2 ^ {n \) log n \ log \ log n}) $.
- 역사적 이유
- " 내가하는 일 ' 사람들이 알고리즘 실행 시간에 big Oh를 사용하는 이유는 무엇입니까? ' 큰 Theta를 사용하면 안됩니다. "-예. 아니, 우리는 더 정확한 진술을해야합니다. 하지만 선택해야한다면 $ \ Theta $!
답변
두 가지 이유가 있습니다. 사람들은 Big Theta보다 Big Oh를 선호합니다.
- 알고리즘의 런타임 복잡성이 최악의 런타임 복잡성으로 정의되는 것은 반드시 아닙니다. $ n $ 길이의 임의 인스턴스에 대한 런타임으로 볼 수도 있습니다. 그런 다음 예를 들어 알고리즘의 런타임 $ t (n) $가 $ \ mathcal {O} (n ^ 2) $에 있다고 작성하면 $ n $ 길이의 입력을 선택하면 항상 커집니다. 일부 상수 $ c $에 대해 $ c \ cdot n ^ 2 $ 함수보다 점근 적으로 느립니다. 따라서 우리는 분명히 최악의 런타임에 대한 설명을 작성합니다.
- 때때로 런타임을 분석 할 때 제공하는 최악의 복잡성이 정말 엄격한 지 확실하지 않은 알고리즘의 복잡성입니다. 예를 들어 행렬 곱셈의 런타임 복잡성 을 생각해보세요. . $ n ^ {2.3728639} $ 런타임이 실제로 최악의 경우인지 확실하지 않습니다. 따라서 런타임은 $ \ mathcal {O} (n ^ {2.3728639}) $에있는 것으로 알려져 있습니다. ” “$ \ Theta (n ^ {2.3728639}) $에 있는지 확실하지 않습니다.
하지만 어떤 경우에는 Big Theta를 제공하는 것이 더 나을 수도 있다는 것이 맞습니다. Big Oh 경계보다 제한됩니다.
댓글
- 광고 1 : 독자 여러분, 조심하세요. 너무 많이 읽어서는 안됩니다 !
답변
(조잡한) 상한은 상한 및 하한은 말할 것도없고 엄격한 상한보다 증명하기 더 쉽습니다.
일부 알고리즘의 런타임은 할 수 없습니다 . em> 상한 / 하한과 동일한 기능으로 주어집니다. 예 : 간단한 정렬 알고리즘은 $ O (n ^ 2) $이지만 $ \ Omega (n) $ 하한이 있습니다.
일부는 $ \ sim $을 통해 점근 적 용어로 성능을 제공하려고 노력합니다. 여기서 $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(예 : 정렬시 비교와 같은 일부 중요한 작업의 수 측면에서 평균 또는 최악의 경우). 즉, 흔들리는 방이지만 양탄자 아래로 휩쓸린 상수는 없습니다.
댓글
- 실행 시간 "에서는 최상의 실행 시간, 최악의 실행 시간 및 평균 실행 시간과 같은 것을 말합니다. 예 : Quicksort에는 $ \ Theta (n ^ 2) $ 최악의 실행 시간과 $ \ Theta (n) $ 최상의 실행 시간이 있습니다. 무증상은 오른쪽 함수에 정의됩니다.
답변
big-Theta 대신 big-Theta를 사용할 수있는 경우 아, 이해하는데 불필요한 어려움을 더하지 않는 한 사용해야합니다. big-Oh 대신에 big-Theta를 사용할 수없는 미묘한 경우가 있습니다. 예 :
다음 문제를 고려하십시오 : 짝수 길이의 배열 정렬. 이 문제를 해결하는 프로그램은 다음과 같습니다. 배열 길이가 홀수이면 즉시 종료하고 배열 길이가 짝수이면 버블 정렬을 수행합니다. 이 알고리즘의 최악의 실행 시간은 무엇입니까?
확실히 $ O (n ^ 2) $이지만 $ \의 의미에서 $ \ Omega (n ^ 2) $는 아닙니다. 일반적으로 Omega $가 정의되어 있지만 최악의 경우 실행 시간은 “$ \ Omega (n ^ 2) $ 무한히 자주”입니다 (경고 : 비표준 용어).
답변
“알고리즘 북이 Theta가 아닌 big-Oh를 사용하는 이유”에 대한 답변 :
Big-Oh는 최악의 경우 분석에 사용되고 Big-Omega는 최상의 경우에만 사용됩니다. 그러나 Big-Theta 측면에서 분석하면 Big-Oh & Big-Omega에 대해 동시에 이야기합니다.
즉. Big-Theta의 경우 Big-Oh == Big-Omega 여야합니다. 그렇지 않으면 Big-Theta에 대해 이야기 할 수 없습니다.
그러므로 (책 / 모든 문서) 어디에서나 Big-Theta, 그들은 Big-Oh & Big-Omega의 복잡성을 제공합니다 (둘 다 동일합니다). 그러나 많은 경우가 같지 않으면 Big-Oh 만 사용합니다. 오, 최악의 경우입니다.