시간 복잡도가 Ө (n²) 인 결정 문제가 있습니까?시간 복잡도가 Ө (n²) 인 결정 알고리즘이 있습니까?
다른 말로하면 가장 잘 알려진 해결책이 으로 증명 된이 N²의 하한을 갖는 결정 문제를 찾고 있습니다.
매트릭스에서 가장 큰 숫자를 찾는 것에 대해 생각했지만 그 문제는 매트릭스가 O (n²)의 입력이므로 솔루션이 선형이라는 것입니다.
문제를 알고있을 필요는 없지만 가상의 것만으로도 충분합니다.
가까운 쌍이 있습니까? r가 입력 파라미터이고 어떤 "어려운"메트릭 공간
r 이하의 거리에 존재하는,
n 점을 부여?
직관적 증거가 :
r가 입력 매개 변수임을 감안할 때, 당신은 모든 지점을 검색 할 수 있습니다.
점에 대해서, 모든 다른 점까지의 거리를 Θ (n)로 계산했습니다.
n 점의 경우 n * Θ (n) = Ө (n²)입니다.
시간 복잡도 : Ө (n²)
어려운 통계 공간이란 무엇입니까? 비 유클리드? –
@ n.m. 그들 중 톤, 비 유클리드도 있습니다. 내 요점은 그것이 사소한 것이되어서는 안된다는 것이다. – gsamaras
접근 가능한 증거가 있습니까? –
은 분명히 당신은 간단한 인터넷 검색을 할 귀찮게하지 않았다. 검색 바에 "O n^2 decision problems"라고 입력하면 다음 PDF가 나타났습니다. [* "O (n^2) *에서의 Frobenius 동전 문제 결정 문제 계산"* (http : // arxiv .org/pdf/1001.0961.pdf) 소음을 유발하는 질문을 게시하기 전에 검색을하십시오. 계정을 만들고 여기에 질문을 게시하는 것보다 시간이 적게 걸렸습니다 ... 30 초 이상 똑똑한 검색을하면 더 나은 것을 찾을 수있을 것입니다. – ray
저를 믿으십시오 - 나는 시도했다. 그리고이 해법은 n^2의 큰 not이 아닙니다. 그것은 n^2/ –
의 큰 O입니다. 저는 여러분이 할 수없는 것이 필요합니다 (그리고 증명되었습니다). 더 빨리 해결할 수 있습니다. 배열에서 가장 큰 숫자를 찾는 것이 큰 것입니다. 이미 거품이 많았습니다. O^2. 하지만 n^2의 큰 need이 필요합니다. –