나는이 문제를 "점의 가장 가까운 쌍"를 brute-force 가장 가까운 쌍의 점; 왜 O (n^2)입니까?
가 왜 무차별 알고리즘의 실행 시간을 최악의 경우는 (그것을 잘 모르는 경우 this 참조) ...이 질문에 대한 바보가 된 기분,하지만 O (n^2)?n = 4라고하면, 검색 공간에서 비교할 수있는 가능한 쌍의 점 쌍이 있습니다. 두 방향에서 두 점을 비교하는 것도 고려해보십시오. 두 점을 두 번 비교하지 않으면 6이됩니다.
O (n^2)가 합산되지 않습니다. 큰 O 표기법에서
실제 비교 횟수는 n*(n-1)/2입니다. 그 값은 n^2/2-n/2입니다. 그러나 big-O 표기법에서는 지배적 인 용어에만 관심이 있습니다. n의 매우 큰 값에서 용어의 계수와 마찬가지로 -n/2 용어는 덜 중요 해집니다. 그래서 우리는 단지 그것이 O(n^2)이라고 말합니다.
Big-O 표기는 걸린 시간 또는 단계 수에 대한 정확한 수식을 제공하지 않습니다. 복잡성/시간의 순서 만 제공하므로 큰 입력에 맞게 크기를 조정할 수 있습니다.
그리고 우리가 계수에 대해 신경 쓰지 않는 이유는 우리가 항상 일정한 요소로 더 빠르거나 느린 컴퓨터를 구입/구축 할 수 있다는 것입니다. 아니면 우리는 훨씬 더 많은 환자 일 수 있습니다. :) – biziclop
좋은 지적. 또한 좋은 구현과 잘못된 알고리즘 구현 간에는 2 가지 요소의 차이를 쉽게 얻을 수 있습니다. –
, 당신은 너무 곱 상수를 인수 분해 할 수
O(k*(n^2)) = O(n^2)
을 아이디어는 (거리 비교가 반사하기 때문에, 영업 예를 들어 1/2) 상수하지 않는 것을 복잡성에 대해 새로운 것을 말해주세요. 그것은 입력의 제곱으로 여전히 커집니다.
알고리즘의 무차별 버전에서는 가능한 모든 쌍의 점을 비교합니다. n 점수 각각에 대해 (n - 1) 다른 점을 비교해보고, 우리가 모든 쌍을 한 번 뽑으면 우리는 (n * (n - 1))/2 비교로 끝납니다. 비관적 인 복잡성이 O(n^2) 인 경우 작업 수가 인 경우 k * n^2으로 바인딩됩니다. Big O 표기법은 정확한 연산 수를 말할 수 없지만 데이터 크기 (n)가 증가하면 비례하는 함수입니다.
우리는 가능한 모든 쌍을 검사해야합니다. N 점을 생각하면 각 점마다 거리를 계산해야하는 N-1 개의 다른 점이 있습니다. 그래서 계산 가능한 총 거리 = N 포인트 * N-1 다른 포인트. 그러나 과정에서 우리는 계산 된 거리를 두 배로 늘립니다. A에서 B 사이의 거리는 A에서 B로 또는 B에서 A로 계산됩니다. 따라서 N * (N-1)/2. 그러므로 O (N^2).
'n = 3'은 어떨까요? 그리고'n = 5'은 어떨까요? – arekolek
계단의 수는 O (n^2)에 비례하며, 동일 할 필요는 없습니다. – Lee