상한, 하한

Question

알고리즘의 상한 또는 하한을 증명한다는 것은 무엇을 의미합니까?

Answer 1

상한을 증명한다는 것은 알고리즘이 사용할 것임을 입증했다는 것을 의미합니다. 더 이상 리소스의 일부 제한.

하한을 증명한다는 것은 알고리즘이 사용할 것임을 입증했다는 것을 의미합니다. ~보다 적지 않은 리소스의 일부 제한.

이 맥락에서 "자원"은 시간, 기억, 대역폭 또는 다른 것일 수 있습니다.

Answer 2

상한과 하한은 알고리즘의 최소 및 최대 "복잡성"과 관련이 있습니다(복잡성 분석에서 매우 구체적인 의미를 갖기 때문에 이 단어를 사용하는 것이 좋습니다).

예를 들어, 우리의 오랜 친구인 버블 정렬을 생각해 보십시오.모든 데이터가 이미 정렬되어 있는 이상적인 경우에 소요되는 시간은 f(n)입니다. n, 목록의 항목 수입니다.목록이 정렬되었는지 확인하려면 데이터 세트를 한 번만 통과(스왑 없이)하면 되기 때문입니다.

데이터가 원하는 순서와 반대로 정렬되는 특히 나쁜 경우에는 소요되는 시간이 f(n²).이는 각 패스가 하나의 요소를 올바른 위치로 이동하고 필요하기 때문입니다. n 모든 요소를 ​​수행하기 위해 전달됩니다.

이 경우, big-O 복잡도는 동일하게 유지되더라도 상한과 하한은 다릅니다.

여담이지만, 버블 정렬은 (보통 좋은 이유로) 많이 비방되지만 특정 상황에서는 의미가 있을 수 있습니다.나는 실제로 대량의 데이터가 이미 정렬되어 있고 목록 끝에 한 번에 하나 또는 두 개의 항목만 추가되는 응용 프로그램에서 이를 사용합니다.하나의 항목을 추가하고 역방향 버블 정렬을 사용하면 새 목록이 한 번에 정렬된다는 것을 보장할 수 있습니다.이는 하한 개념을 보여줍니다.

실제로 목록이 정렬되었는지 여부를 나타내는 추가 데이터를 제공하기만 하면 하한을 f(1)로 설정하는 버블 정렬을 최적화할 수 있습니다.정렬 후에 이를 설정하고 끝에 항목을 추가할 때 이를 지웁니다.

Answer 3

바운드 (위 또는 아래)가 무엇이든, 우리는 항상 우리가 고려할 수있는 최악의 입력에 대해 이야기하고 있습니다. 예를 들어, 정렬 할 때 최악의 사례는 분류되지 않은 입력 목록이라고 가정합니다.

내 이해는 그게됩니다 문제 하한이 있습니다. 예를 들어, 비교 기반 분류의 하한은 오메가 (n log n)라고 말합니다. 우리는 특정 비교 기반 분류에 대해 가정하지 않습니다. 연산 우리는 사용. 알고리즘 (Merge 정렬, 빠른 정렬 등)이 무엇이든, 우리는이 경계의 Omega (n log n)보다 더 잘할 수 없습니다. 하한은 직관적으로, 특정 얼마나 힘든지 알려줍니다. 문제 이다.

우리가 특정에 대해 이야기 할 때 연산, 그런 다음 우리는 상한에 대해 이야기합니다. 예를 들어, 우리는 기포 정렬의 상한이 O (n^2)이고 병합 정렬의 상한은 O (n log n)라고 말합니다. 직관적으로 상한은 우리에게 특별한 지 알려주세요 연산 문제를 해결하는 것입니다.