알고리즘 분석 과정을 수강하고 있으며 Java에서 알고리즘 숙제를하고 있습니다. 나는이 프로그램을 썼고 아주 잘 작동한다. 그러나 선생님은 여분의 점에 대한 최악의 경우의 비대증 결과와 비교하여보고하고 싶었습니다. 무슨 뜻이에요? 어떻게 비교할 수 있습니까? 첫 번째 것은 convex hull 알고리즘이고 두 번째 알고리즘은 배낭 알고리즘입니다. 볼록 선체의 복잡도는 최악의 경우입니다. 왜 그가 최악의 경우를 원했던가? 내 배낭 알고리즘의 복잡도는 (n * 2^n)입니다. 너 나 좀 도와 줄 수있어?배낭 알고리즘 및 볼록 선체
알고리즘의 점근 적 복잡성을 비교하고 일부 데이터로 구체화해야합니다. 이렇게하면 복잡성과 실제 런타임 간의 연결에 대한 개요가 제공됩니다.
그들은 최악의 경우를 요구합니다. 보통 대다수의 해결책을 제시 할 수 있기 때문입니다. 예를 들어 알고리즘이 첫 번째 시도에서 솔루션에 걸려 넘어지면 배낭이 n = 1000으로 즉시 작동하지만 사용자가 해당 크기의 입력에 대해 작동 할 것이라고 약속 할 수는 없습니다 (너무 오래 걸림).
이제 복잡성이 있으므로 O (n^3) < O (n2^n)이므로 복잡성을 비교할 때 선체가 더 빠릅니다. 이제 n = 1,2,3,4,5, 10, 20, 25, 30, 50, 100, 500, 1000의 예제를 사용하여 솔루션을 구하십시오. n의 값이 작은 경우에는 타이밍이 거의 같고 복잡성에 따라 행동하지 않지만 n이 커지면 합리적인 시간에 O (n^3)가 끝나고 O (n2^n) 너무 오래 걸릴 것입니다 (몇 분 후에 멈추십시오). 결과를 플롯하고 x^3 및 x2^x 함수의 모양과 비교하십시오.
@Sorin 고맙습니다. – edithpiaf
O (n log n)에서 배낭 결정 문제를 해결 했습니까? 축하합니다. 언제 Turing Award를 수령합니까? 힌트 : 배낭에 대한 결정 문제는 NP 어렵다 ... 이것은 또한 최악의 분석이 중요한 이유에 대한 힌트 일 수도있다. – dhke
그건 실제로 두 가지 질문입니다. 정확히 그 질문은 무엇입니까? 최악의 경우의 점근 현상을 연구하는 것이 왜 합리적입니까? – Codor
정확한 질문은 다양한 포인트 수에 대한 런타임을 측정하고 수렴 동작을 관찰하는 것입니다. 최악의 경우의 결과와 비교하십시오. 결과가 최악의 분석을 확인합니까? @ 코도 – edithpiaf