नींद की तरह की जटिलता क्या है?

Question

इस तरह के एल्गोरिदम को देखते हुए आप इसकी समय जटिलता कैसे व्यक्त करते हैं?

Originally presented here (partial archive)।

#!/bin/bash 
function f() { 
sleep "$1" 
echo "$1" 
} 
while [ -n "$1" ] 
do 
    f "$1" & 
    shift 
done 
wait 

example usage: 
./sleepsort.bash 5 3 6 3 6 3 1 4 7 

Answer 1

मुझे लगता है कि paxdiablo निकटतम है, लेकिन सही कारण के लिए नहीं । समय जटिलता असली हार्डवेयर जैसे कैश आकार, मेमोरी सीमाओं और इस मामले में प्रक्रियाओं की सीमित संख्या और शेड्यूलर के संचालन पर मुद्दों को अनदेखा करती है।

Wikipedia page for Time complexity मैं कहना चाहता हूँ जवाब है कि आप क्रम जटिलता निर्धारित नहीं कर सकता क्योंकि अगर यह परिभाषित किया गया है के रूप में है के आधार पर:

समय जटिलता आमतौर पर प्रदर्शन किया प्राथमिक आपरेशन की संख्या की गणना का अनुमान है एल्गोरिदम द्वारा, जहां एक प्राथमिक ऑपरेशन करने के लिए निश्चित समय लगता है। इस प्रकार एल्गोरिदम द्वारा किए गए समय की मात्रा और प्राथमिक संचालन की संख्या सबसे अधिक स्थिर कारक से भिन्न होती है।

फिर हम इस एल्गोरिदम की रनटाइम जटिलता के बारे में बात नहीं कर सकते हैं क्योंकि प्राथमिक ऑपरेशन लेने का समय इतना अलग है, कि लिया गया समय निरंतर कारक से अधिक भिन्न होगा।

Answer 2

O(max(input)+n)

जटिलता सिर्फ व्यक्त करने के लिए है क्योंकि ज्यादातर छँटाई एल्गोरिदम नास्तिक डेटा कर रहे हैं अजीब दिखाई देता है। डेटा की मात्रा के साथ उनका समय तराजू, डेटा स्वयं ही नहीं।

FWIW, जैसा कि here पर इंगित किया गया है, यह डेटा सॉर्ट करने के लिए विश्वसनीय एल्गोरिदम नहीं है।

Answer 3

यदि आप धागे को पढ़ते हैं तो आप देखेंगे कि आपका प्रश्न पहले से ही उत्तर दिया गया है। समय जटिलता O(max(input)) है और परिचालन जटिलता (संचालन की संख्या) O(n) है।

Answer 4

उस समय एल्गोरिदम की जटिलता और प्रक्रिया जटिलता दोनों O(braindead) हैं।

डेटा सेट में पर्याप्त बड़े मूल्य के साथ, आप सूरज विस्फोट होने तक उत्तर का इंतजार करेंगे।

एक पर्याप्त रूप से बड़े डेटा के साथ आकार सेट, आप करेंगे

• (1) अपनी प्रक्रिया सीमा तक नहीं पहुंच; और
• (2) पाते हैं कि शुरुआती नींद बाद वाले लोगों के शुरू होने से पहले खत्म हो जाएगी, जिसका अर्थ है (2,9,9,9,9,9,...,9,9,1)1 और 2 सही ढंग से सॉर्ट नहीं करेगा।

इस मामले में समय जटिलता अप्रासंगिक है। आप को "गलत" से कम अनुकूलित नहीं कर सकते हैं।

यह जटिलता विश्लेषण का उपयोग करने के डेटा सेट आकार में परिवर्तन के रूप एल्गोरिदम तुलना करने के लिए ठीक है, लेकिन नहीं जब एल्गोरिदम पहली जगह में ऊटपटांग हैं :-)

Answer 5

एक बिंदु जिसे कोई भी संबोधित नहीं करता है वह यह है कि sleep एस लागू किए गए हैं। अंत में वे कहीं भी शेड्यूलर में समाप्त होते हैं, और परिचालन जटिलता शेड्यूलिंग एल्गोरिदम पर निर्भर करती है। उदाहरण के लिए, यदि sleep एस को प्राथमिकता कतार में ईवेंट के रूप में रखा जाता है तो आप जटिलता ओ (एन लॉग एन) जटिलता के साथ, हेपसोर्ट के बराबर कुछ के साथ समाप्त हो जाएंगे। एक बेवकूफ शेड्यूलिंग एल्गोरिदम का परिणाम ओ (एन^2) हो सकता है।

Answer 6

हालांकि रैखिक जैसा दिखता है, मुझे लगता है कि जटिलता अभी भी ओ है (लॉग (एन) * अधिकतम (इनपुट))।

जब हम एसिम्प्टोटिक समय जटिलता के बारे में बात करते हैं, तो इसका मतलब है कि जब एन अनगिनत रूप से बड़ा होता है तो कितना समय लगता है।

प्रक्रियाओं सो n सेकंड और मद्देनजर:

एक comparasion आधारित छँटाई एल्गोरिथ्म O (n * लॉग (एन)), और नींद-क्रमबद्ध तुलना में तेजी से नहीं किया जा सकता है, वास्तव में comparasion आधारित है। ओएस को सभी नींद की प्रक्रिया से कम से कम सोने का समय खोजने की ज़रूरत है, और यदि समय के बारे में है तो उसे उठाएं।

इसे प्राथमिकता कतार की आवश्यकता होगी, जिसमें एक तत्व डालने वाला ओ (लॉगएन) समय लेता है, और ओ (1) न्यूनतम तत्व ढूंढता है, और ओ (लॉगएन) न्यूनतम तत्व को हटा देता है।

जब एन बहुत बड़ा हो जाता है, तो प्रक्रिया को जागृत करने में 1 सेकंड से अधिक समय लगेगा, जो इसे ओ (एन) से बड़ा बनाता है।

Answer 7

मैं जॉर्डन के साथ हूं, सिवाय इसके कि मुझे लगता है कि दीवार घड़ी की जटिलता ओ (2^मीटर) के रूप में बेहतर व्यक्त की जाती है जहां मीटर ओ (अधिकतम (इनपुट)) के बजाय प्रत्येक आइटम का आकार होता है।

यदि प्रत्येक आइटम में आकार एम है, तो सबसे बड़ी वस्तु में पूर्णांक मान 2^मीटर (शून्य से एक होगा, लेकिन कोई भी इसके बारे में परवाह नहीं करेगा)। निर्माण के द्वारा, एल्गोरिदम को सेट-अप समय को 1 से छोटा होने की आवश्यकता होती है, स्थिर।

तो वॉल-घड़ी-समय जटिलता ओ (2^मीटर), ऑपरेशन-गिनती जटिलता ओ (एन)।

एक संशोधित एल्गोरिदम खाता सेट-अप समय में ले जाने की संभावना में घड़ी-घड़ी की जटिलता ओ (2^एम + एन) होगी। उदाहरण के लिए, यह शुरुआत में वर्तमान समय को नोट कर सकता है, base_time = start_time + k*len(list) (कुछ उचित निरंतर के लिए) की गणना करें, फिर base_time+i समय तक धागे सोएं। फिर k*len(list) स्पष्ट रूप से ओ (2^एम + एन) के लिए ओ (एन) और i ओ (2^मीटर) है, जैसा कि पहले है।