प्लॉटिंग (कॉर्मन) लाल-काले पेड़ डालने के अजीब परिणाम

Question

मैंने पार्मन में रेड-ब्लैक पेड़ों में कॉर्मन के Introduction to Algorithms में छद्म कोड के अनुसार लागू किया।

मैं अपने ही आँखों में देखने के लिए कि मेरे insert वास्तव में O(logn) तो मैं समय यह पेड़ में n=1, 10, 20, ..., 5000 नोड्स सम्मिलित करने के लिए ले जाता है साजिश रची है चाहता था।

x धुरी n है और y धुरी समय यह मिलीसेकेंड में ले लिया है:

यह परिणाम है।

मेरे लिए ग्राफ लॉगरिदमिक से अधिक रैखिक दिखता है। क्या समझा सकता है?

Answer 1

ठीक है, इसलिए ग्राफ आपके पेड़ में 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 का:

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

---

क्रिस टेलर टिप्पणी में कहा गया है कि अगर आप f(n)/n साजिश, आप एक लॉग ग्राफ़ दिखाई देगा। ऐसा इसलिए है क्योंकि 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 पर चलता है। यदि इसमें दो सेकंड और बीस सेकंड लगते हैं, तो रैखिक विकास समझ में आता है। यदि यह कम लेता है, तो लॉगरिदमिक समझ में आता है। यदि आप अधिकतर "सरल" कार्यों पर बारीकी से ज़ूम करते हैं, तो परिणाम बहुत रैखिक दिखते हैं।

Answer 3

किसी भी 'क्यों' प्रश्न के लिए हमेशा कुछ हद तक अटकलें होती हैं। मुझे संदेह होगा कि आप जो कूद देख रहे हैं वह सिस्टम मेमोरी प्रबंधन से संबंधित है। अगर सिस्टम को निरंतर विकास के लिए एक बड़ी मेमोरी स्पेस आवंटित करनी है, तो यह पूरे कार्यक्रम की प्रक्रिया को पूरा करने के लिए एक निश्चित समय जोड़ देगा। यदि आपने नोड्स को 'पेलोड' फ़ील्ड जोड़ा है, इस प्रकार आवश्यक संग्रहण स्थान की मात्रा में वृद्धि हुई है, और मैं सही हूं, तो कूद अक्सर अधिक होता है।

वैसे भी अच्छा ग्राफ।