점근 표기법 - n (log n) (log n)가 단순화됩니까?

Question

n 로그 n 단계 (예 : heapsort)를 취하는 알고리즘이있는 경우 단계가 로그 N 시간 (예 : 0에서 n-1 범위의 "큰"정수의 비교/교환)이 전체 프로세스.

분명히 우리는 "n (log n) (log n)"이라고 말할 수 있지만, 나는 이것을 "n log n"으로 단순화 할 수 없다는 것을 스스로 확신 시키려고 노력하고 있습니다. 동시에, 나는 내가 할 수 있다고 주장하는 본능을 정당화하는 데 어려움을 겪고 있습니다.

내 본능이 이것에 대해 명백한 잘못입니까?

편집하다

내 간단한 예방 접종을 복제하는 것이 문제를 복잡하게 만든 것 같습니다. 오, 음.

질문의 진정한 이유는 종종 복잡성이 알려진 표준 알고리즘을 가지고 있지만 다른 기본 컨테이너를 사용하여 구현하여 개별 단계가 O (1) 대신 O (log n)이기 때문입니다. 예를 들어 Hopcrofts Automaton Minimization 알고리즘은 O (n log n)입니다. 그러나 상태, 전환 및 중간 결과에 이진 트리 컨테이너를 사용하기 시작하면 단계 자체가 O (log n) - O (n log n)가 O (1) 액세스의 가정이 유효하지 않기 때문에 더 이상 유효하지 않습니다.

그럼에도 불구하고 사람들은 N 상태와 M 전이가 있다고 주장 할 것이지만, 전이 주석의 수가 일정하고 오토마타가 더 결정적이지 않다고 가정 할 때, N과 M은 Automata와 선형으로 관련되는 경향이있다.

나는 과거에 이것에 대해 너무 걱정하지 않았습니다. 내가 함께 일하는 경우는 크게 크지 않습니다. 그러나 저는 Automata 코드의 주요 리팩토링을하고 있으며, 내가 갈 때 일부 주요 알고리즘에 대해 수학을 제대로 할 수 있다고 생각했습니다.

편집하다

나는 또한 "n (log n) (log n)"이 잘못되었다고 확신하고 있습니다.

A가 O (B log B) 인 경우 B는 O (log C) 인 경우 A는 C 측면에서 A는 무엇입니까?

Answer 1

모순의 증거는 다음과 같습니다.

함수 f (n) = n (log n) (log n)이라고 가정 해 봅시다. 우리가 그것이 또한 theta (n log n)라고 생각한다고 가정하므로, 즉 f (n) <= a * n log n이 큰 n에 대해 보유하는 A가 있습니다.

이제 f (2^(a+1))를 고려하십시오.

f (2^(a+1)) = 2^(a+1) * log (2^(a+1)) * log (2^(a+1)) = 2^(a+1) * log (2^(a+1)) * (a+1), 이것은 A * 2^(a+1) * log (2^(a+1))보다 분명히 큽니다. 모순이 있습니다. 따라서 f (n)은 n log n 함수가 아닙니다.

Answer 2

일반적으로 힙 정렬의 경우 N은 힙의 항목 수를 나타내는 반면, 큰 정수의 경우 N은 아마도 가능한 값의 상한을 나타냅니다. 일반적으로, 이것들은 관련 될 필요가 없으므로 다소 n log n log m입니다 (여기서 m은 항목이 취할 수있는 범위).

특정 응용 프로그램에서, 아마도 큰 정수는 특정 분포를 따릅니다. 예를 들어, 그것들이 모두 10^20 미만인 것으로 알려져있을 수 있습니다. 그렇다면 비교 작업은 일정한 시간이 걸립니다 (10^20의 상한에 의해 결정 됨). 그런 다음 로그 M도 일정하고 전체 복잡성은 O (N log n)에 있습니다.

Answer 3

당신은 줄일 수 없습니다 n (log n) (log n) 에게 n (log n) 단순히 일정한 요인에 의한 감소가 아니기 때문입니다.

무슨 일이야 n (log n)2?

Answer 4

좋아요, 프로그램의 일반적인 복잡성 측정 값은 다음과 같습니다.

복잡성 o (f (n))은 존재한다는 것을 의미합니다. c, 종료되기 전에 상응하는 튜링 머신의 수는 c*f (n)를 넘지 않아서 n은 입력 길이입니다.

이 정의에서는 정수 번호가 임의로 클 수 있고 산술 작업은 O (n)에 따라 함수를 증가시킬 수 있기 때문에 모든 것이 고려됩니다.

그러나 우리가 튜링 머신을 직접 프로그래밍하고 있다면, 당신의 질문은 발생하지 않았을 것입니다. 실제 세계에서 우리는 추상적 인 것을 선호합니다. 프로그램을 실행하는 데 필요한 "단계"를 여전히 계산하지만 특정 작업이 취한다고 가정합니다. 한 단계. 우리는 다른 이유로 다음과 같이 가정합니다.

• 그것은 CPU의 실제 작업과 비슷할 수 있으며, 각 32 비트 정수 추가는 실제로 한 단계입니다 (그리고 실제로는 그것을 남용하는 알고리즘이 있습니다.
• 동일한 도메인에서 다른 알고리즘을 비교합니다 (예 : 비교 수를 측정하여 배열 분류를 비교).

이 경우 (첫 번째 편집) 복잡성 측정 값을 구체화하려면 O (Log N) 단계를 수행하는 것으로 간주 된 한 단계를 취한다고 생각한 경우 콘크리트의 양을 사용하는 경우 O에서 기능을 곱해야합니다. 단계는 O (log n)의 계수만큼 증가합니다. 따라서 총 복잡성은 O (n로그 n로그 N).

---

두 번째 편집에 관해서는 다른 상황입니다. 알고리즘이 O (n로그 N). 그러나 당신은 입력이 구성되어 있음을 알고 있습니다 M 숫자, 각각 log K 숫자, 그래서`n = o (mlog k) (우리는 분리기 등을 설명해야합니다). O (m * log k * (log m + log k))와 같이 전반적인 복잡성을 작성하는 것이 수학적으로 정확하므로 여기에는 아무런 문제가 없습니다. 그러나 일반적으로 우리는 다른 알고리즘을 비교할 공통적 인 기초를 찾기 위해 불필요한 세부 사항을 추출합니다.