O (n {log n}^k) 시간 (k> 1)에서 실행되는 많은 알고리즘이 있습니다. 당신이 나에게있는 모든 문제 에 대한 몇 가지 참조 제공 할 수있는 경우 Omega {(n (logn)^k)}의 하한을 어떻게 증명할 수 있습니까? [k> 1]
그것은 매우 도움이 될 것입니다 : 오메가 \
을 {(n은 {로그 N}^K)}, 하한 곳 K> 1.
k = 1에 대한 예가 많이있다. 가장 가까운 쌍/정렬.
다음은 k = 2에 대한 인위적인 예제입니다.
너는 nxn 배열을 가지고있다. 배열의 각 행이 정렬됩니다.
각 행에는 행의 모든 요소가 그 행에서 홀수 번 발생하는 1을 제외하고 (해당 행에서) 짝수 번 발생하는 속성이 있습니다.
각 행의 "홀수"요소를 찾습니다.
이것은 오메가 (nlog^2n) 하한 (O (nlog^2n) 알고리즘이 있음)을 증명할 수 있습니다.
1 행의 경우, 여기에 증거가 있습니다 (stackoverflow) : How can I find a number which occurs an odd number of times in a SORTED array in O(n) time? 이는 오메가 (로그^2 n) 하한을 증명합니다. 이 문제에 대한 하한선을 쉽게 증명합니다.
컴퓨터 기하학의 알고리즘이나 알고리즘은 무엇입니까? 또한,이 숙제는 무엇입니까? – Jacob