플롯팅시 이상한 결과가 나타남 (Cormen) 레드 - 블랙 트리 삽입

Question

Cormen의 Introduction to Algorithms에있는 의사 코드에 따라 Python의 Red-Black 트리에서 구현되었습니다.

내 insert이 실제로 O(logn) 인 것을 내 눈으로보고 싶었으므로 트리에 n=1, 10, 20, ..., 5000 개의 노드를 삽입하는 데 걸리는 시간을 계획했습니다. x이시킴으로써 행한다

이 n하고 y이시킴으로써 행한다는 밀리 초에 걸린 시간입니다 :

이

은 결과입니다.

내게는 그래프가 로그보다 선형으로 보입니다. 그것을 설명 할 수있는 것은 무엇입니까?

Answer 1

좋아요, 그래야 그래프에 n 요소를 트리에 삽입하는 비용이 표시됩니다. 여기서 x 축은 삽입 한 요소의 수이고 y 축은 총 시간입니다.

n 개의 요소를 트리에 삽입하는 데 걸리는 시간을 합한 함수를 호출 해 보겠습니다. f(n).

그리고 우리는 f의 모양에 대한 대략적인 아이디어를 얻을 수 있습니다 :

f(1) < k*log(1)     for some constant k. 

f(2) < k*log(1) + k*log(2)  for some constant k 

... 

f(n) < k * [log(1) + log(2) + ... + log(n)] for some constant k. 

인해 로그가 어떻게 작동하는지에를, 우리는 log(1) + ... + log(n)를 축소 할 수 있습니다 :

f(n) < k * [log(1*2*3*...*n)]  for some constant k 

f(n) < k * log(n!)    for some constant k 

우리는 위키 백과에서 좀 걸릴 수 있습니다 어떤 log(n!) 모양의 graph을 볼 수 있습니다. 기사의 그래프를보십시오. 너에게 꽤 익숙해 져야한다.:)입니다

는

, 당신이 실수로 이런 짓을했다고 생각 :

for n in (5000, 50000, 500000): 
    startTime = ... 
    ## .. make a fresh tree 
    ## insert n elements into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

오히려 나무로 하나 개의 요소를 삽입하는 개별 비용보다 크기 n의 트리를 구성하는 총 시간을 꾸몄다 크기 n의 : 당신이 f(n)/n 음모 경우 크리스 테일러 (Chris Taylor)는 코멘트에 주목

for n in range(50000): 
    startTime = ... 
    ## insert an element into the tree 
    stopTime = ... 
    ## record the tuple (n, stopTime - startTime) for plotting 

---

, 당신은 로그 그래프를 볼 수있다. log(n!)에 대한 매우 긴밀한 근사값은 n*log(n)입니다 (위키피디아 페이지 참조).

f(n) < k * log(n!)    for some constant k 

를 얻을 : 그래서 우리는 우리의 경계로 돌아갈 수

f(n) < k * n * log(n)    for some constant k 

를 그리고 지금 당신이 n에 의해 f(n)를 나눈다면, 그래프가 이상 경계 할 것을 쉽게 볼 수 있어야 있어요 대수의 형태.

Answer 2

5000은 로그를 실제로 "볼"수 없을만큼 커야합니다. 시도는 50000 및 500000입니다. 2 초와 20 초가 걸리면 선형 성장이 이치에 맞습니다. 그것이 적다면, 로그가 의미가 있습니다. 대부분의 "단순"기능을 면밀히 살펴보면 결과는 꽤 선형으로 보입니다.

Answer 3

'이유'질문에는 항상 몇 가지 추측이 있습니다. 나는 당신이보고있는 점프가 시스템 메모리 관리와 관련이 있다고 의심 할 것이다. 시스템이 지속적인 증가를 위해 더 큰 메모리 공간을 할당해야한다면 전체 프로그램의 처리를 완료하는 데 일정 시간이 추가됩니다. 노드에 '페이로드'필드를 추가하여 필요한 저장 공간을 늘리고 올바른 경우 점프가 더 자주 발생합니다.

좋은 그래프, 그건 그렇고.