나는 먼저 O(n*log(n)) 시간에 뭔가를 수행 한 다음 다른 시간에 O(n^2) 시간을합니다. 나는 총 복잡성 log(n) + n 이후O (n * log n) 작업을 수행하고 O (n^2)가 작동하는 코드의 복잡성은 무엇입니까?
O(n*log(n) + n^2)
= O(n*(log(n) + n))
= O(n^2)
가 + n에 의해 지배 될 것이라고 수정하고 있는가?
O(n log n)은 O(n^2)의 하위 집합이므로 올바른 내용입니다. 그러나 공식을 증명하는 것은 적절한 상수를 선택하고 구성하는 것으로 구성됩니다.
두 호출 확률이 같으면 올바른 것입니다. 그러나 두 가지 가능성이 같지 않은 경우 드문 비싼 통화 (n²)를 많은 빠른 통화 (nlog (n))로 분할하는 상환 분석을 수행해야합니다.
예를 들어 빠른 정렬 (일반적으로 nlog (n) 걸리지 만 rarly는 n²)을 사용하면 상각 처리 된 분석으로 인해 평균 실행 시간이 nlog (n)임을 증명할 수 있습니다.
나는 그 질문에 대해 오해했다고 생각합니다. 나는 O (n log n) 시간에 실행되는 알고리즘과 O (n²) 시간에 실행되는 알고리즘의 두 단계로 구성된 알고리즘에 대해 생각합니다. 가능성은 없습니다. – ruakh
그러면 코도 응답이 가장 좋습니다. – gartenkralle
복잡도 분석 규칙 중 하나는 지수가 낮거나 낮은 요인을 제거해야한다는 것입니다.
nlogn vs n^2 (divide both by n)
logn vs n
logn 복잡성 n은, nlogn 값 정말로 큰 O (nlogn + N^2) 인 경우
매우 복잡한 방정식에서 제거 할 수있는 것보다, N보다 작 n^2와 비교하면 의미가 없습니다. 따라서 이것을 제거하고 O (n^2)로 다시 쓰십시오.
맞습니다. n² 항이 지배적입니다. –