क्या प्रोग्रामिंग रूप से एल्गोरिदम की समय जटिलता की गणना करने का कोई तरीका है? उदाहरण के लिए, मैं fibonacci(n) फ़ंक्शन की जटिलता की गणना कैसे कर सकता हूं?क्या कोई प्रोग्राम एल्गोरिदम की जटिलता की गणना कर सकता है?
halting problem की अनिश्चितता का कहना है कि आप यह भी नहीं बता सकते कि कोई एल्गोरिदम समाप्त हो गया है या नहीं। मुझे इस बात से बहुत यकीन है कि यह आमतौर पर एल्गोरिदम की जटिलता को हल नहीं कर सकता है।
fibbonacci() के अंदर उपयोग किए गए अंकगणितीय परिचालन, मेमोरी एक्सेस और मेमोरी स्पेस की गणना करें या जो भी हो, उसके निष्पादन समय को मापें। विभिन्न इनपुट के साथ ऐसा करें, उभरते रुझान, असीमित व्यवहार देखें।
सामान्य रूप से नहीं। अगर एल्गोरिदम में नेस्टेड सरल for लूप शामिल हैं, उदा।
for (int i=a; i<b; ++i)
तो आप जानते हैं कि यह (b-a) चरणों योगदान देगा। अब, यदि b या a या दोनों n पर निर्भर करते हैं, तो आप उससे जटिलता प्राप्त कर सकते हैं। हालांकि, अगर आप अधिक विदेशी कुछ, जैसे
for (int i=a; i<b; i=whackyFunction(i))
है तो आप वास्तव में समझने के लिए क्या whackyFunction(i) करता है की जरूरत है।
इसी प्रकार, break कथन इसे खराब कर सकते हैं, और while कथन एक खोया कारण हो सकता है क्योंकि यह संभव है कि आप यह भी बताने में सक्षम न हों कि लूप समाप्त हो गया है या नहीं।
cyclomatic complexity जैसे सामान्य उपाय आपको अपने कोड के अधिक जटिल भागों का एक विचार देने में उपयोगी हैं, लेकिन यह अपेक्षाकृत सरल तंत्र है।
हालांकि सभी मामलों के लिए यह असंभव है (जब तक कि आप अपना कोड पार्सर नहीं चलाते हैं और केवल लूप को देखते हैं और उनके मूल्यों पर क्या प्रभाव पड़ता है), फिर भी ऊपरी बाउंड वाले काले बॉक्स परीक्षण के रूप में करना संभव है निर्धारित समयसीमा। ऐसा कहने के लिए, कुछ वैरिएबल है जो यह निर्धारित करने के लिए सेट है कि एक बार प्रोग्राम का निष्पादन इस बार गुजरता है, इसे हमेशा के लिए चल रहा माना जाता है।
इससे आपका कोड इस तरह दिखता है (त्वरित और गंदा कोड क्षमा करें यह थोड़ा वर्बोज़ है और गणित बड़ी शक्तियों के लिए बंद हो सकता है जिसे मैंने चेक नहीं किया है)।
इसे यादृच्छिक रूप से कुछ उत्पन्न करने के बजाय इनपुट मूल्यों की एक सेट सरणी का उपयोग करके और मूल्यों की एक विस्तृत श्रृंखला की जांच करके, आप किसी भी अन्य इनपुट के विरुद्ध किसी इनपुट को जांचने और सभी निर्धारित करने में सक्षम होना चाहिए विधि अवधि के पैटर्न।
मुझे यकीन है कि O को यहां दिखाए गए दिए गए नंबरों के सेट के बीच गणना करने के लिए बहुत बेहतर (अर्थात् अधिक सटीक) तरीके हैं (जो तत्वों के बीच रन टाइम को जोड़ने के लिए उपेक्षा करते हैं)।
static void Main(string[] args)
{
var sw = new Stopwatch();
var inputTimes = new Dictionary<int, double>();
List<int> inputValues = new List<int>();
for (int i = 0; i < 25; i++)
{
inputValues.Add(i);
}
var ThreadTimeout = 10000;
for (int i = 0; i < inputValues.Count; i++)
{
int input = inputValues[i];
var WorkerThread = new Thread(t => CallMagicMethod(input)) { Name = "WorkerThread" };
sw.Reset();
Console.WriteLine("Input value '{0}' running...", input);
sw.Start();
WorkerThread.Start();
WorkerThread.Join(ThreadTimeout);
sw.Stop();
if (WorkerThread.IsAlive)
{
Console.WriteLine("Input value '{0}' exceeds timeout", input);
WorkerThread.Abort();
//break;
inputTimes.Add(input, double.MaxValue);
continue;
}
inputTimes.Add(input, sw.Elapsed.TotalMilliseconds);
Console.WriteLine("Input value '{0}' took {1}ms", input, sw.Elapsed.TotalMilliseconds);
}
List<int> indexes = inputTimes.Keys.OrderBy(k => k).ToList();
// calculate the difference between the values:
for (int i = 0; i < indexes.Count - 2; i++)
{
int index0 = indexes[i];
int index1 = indexes[i + 1];
if (!inputTimes.ContainsKey(index1))
{
continue;
}
int index2 = indexes[i + 2];
if (!inputTimes.ContainsKey(index2))
{
continue;
}
double[] runTimes = new double[] { inputTimes[index0], inputTimes[index1], inputTimes[index2] };
if (IsRoughlyEqual(runTimes[2], runTimes[1], runTimes[0]))
{
Console.WriteLine("Execution time for input = {0} to {1} is roughly O(1)", index0, index2);
}
else if (IsRoughlyEqual(runTimes[2]/Math.Log(index2, 2), runTimes[1]/Math.Log(index1, 2), runTimes[0]/Math.Log(index0, 2)))
{
Console.WriteLine("Execution time for input = {0} to {1} is roughly O(log N)", index0, index2);
}
else if (IsRoughlyEqual(runTimes[2]/index2, runTimes[1]/index1, runTimes[0]/index0))
{
Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N)", index0, index2);
}
else if (IsRoughlyEqual(runTimes[2]/(Math.Log(index2, 2) * index2), runTimes[1]/(Math.Log(index1, 2) * index1), runTimes[0]/(Math.Log(index0, 2) * index0)))
{
Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N log N)", index0, index2);
}
else
{
for (int pow = 2; pow <= 10; pow++)
{
if (IsRoughlyEqual(runTimes[2]/Math.Pow(index2, pow), runTimes[1]/Math.Pow(index1, pow), runTimes[0]/Math.Pow(index0, pow)))
{
Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N^{2})", index0, index2, pow);
break;
}
else if (pow == 10)
{
Console.WriteLine("Execution time for input = {0} to {1} is greater than O(N^10)", index0, index2);
}
}
}
}
Console.WriteLine("Fin.");
}
private static double variance = 0.02;
public static bool IsRoughlyEqual(double value, double lower, double upper)
{
//returns if the lower, value and upper are within a variance of the next value;
return IsBetween(lower, value * (1 - variance), value * (1 + variance)) &&
IsBetween(value, upper * (1 - variance), upper * (1 + variance));
}
public static bool IsBetween(double value, double lower, double upper)
{
//returns if the value is between the other 2 values +/- variance
lower = lower * (1 - variance);
upper = upper * (1 + variance);
return value > lower && value < upper;
}
public static void CallMagicMethod(int input)
{
try
{
MagicBox.MagicMethod(input);
}
catch (ThreadAbortException tae)
{
}
catch (Exception ex)
{
Console.WriteLine("Unexpected Exception Occured: {0}", ex.Message);
}
}
और एक उदाहरण के उत्पादन:
Input value '59' running...
Input value '59' took 1711.8416ms
Input value '14' running...
Input value '14' took 90.9222ms
Input value '43' running...
Input value '43' took 902.7444ms
Input value '22' running...
Input value '22' took 231.5498ms
Input value '50' running...
Input value '50' took 1224.761ms
Input value '27' running...
Input value '27' took 351.3938ms
Input value '5' running...
Input value '5' took 9.8048ms
Input value '28' running...
Input value '28' took 377.8156ms
Input value '26' running...
Input value '26' took 325.4898ms
Input value '46' running...
Input value '46' took 1035.6526ms
Execution time for input = 5 to 22 is greater than O(N^10)
Execution time for input = 14 to 26 is roughly O(N^2)
Execution time for input = 22 to 27 is roughly O(N^2)
Execution time for input = 26 to 28 is roughly O(N^2)
Execution time for input = 27 to 43 is roughly O(N^2)
Execution time for input = 28 to 46 is roughly O(N^2)
Execution time for input = 43 to 50 is roughly O(N^2)
Execution time for input = 46 to 59 is roughly O(N^2)
Fin.
कौन सा जादू विधि से पता चलता दिया आदानों के लिए संभावना O(N^2) है +/- 2% विचरण
और यहाँ एक और परिणाम:
Input value '0' took 0.7498ms
Input value '1' took 0.3062ms
Input value '2' took 0.5038ms
Input value '3' took 4.9239ms
Input value '4' took 14.2928ms
Input value '5' took 29.9069ms
Input value '6' took 55.4424ms
Input value '7' took 91.6886ms
Input value '8' took 140.5015ms
Input value '9' took 204.5546ms
Input value '10' took 285.4843ms
Input value '11' took 385.7506ms
Input value '12' took 506.8602ms
Input value '13' took 650.7438ms
Input value '14' took 819.8519ms
Input value '15' took 1015.8124ms
Execution time for input = 0 to 2 is greater than O(N^10)
Execution time for input = 1 to 3 is greater than O(N^10)
Execution time for input = 2 to 4 is greater than O(N^10)
Execution time for input = 3 to 5 is greater than O(N^10)
Execution time for input = 4 to 6 is greater than O(N^10)
Execution time for input = 5 to 7 is greater than O(N^10)
Execution time for input = 6 to 8 is greater than O(N^10)
Execution time for input = 7 to 9 is greater than O(N^10)
Execution time for input = 8 to 10 is roughly O(N^3)
Execution time for input = 9 to 11 is roughly O(N^3)
Execution time for input = 10 to 12 is roughly O(N^3)
Execution time for input = 11 to 13 is roughly O(N^3)
Execution time for input = 12 to 14 is roughly O(N^3)
Execution time for input = 13 to 15 is roughly O(N^3)
जो दिखाता है कि जादू विधि O(N^3) में दी गई है डालता है +/- 2% भिन्नता
तो प्रोग्रामिंग रूप से एल्गोरिदम की जटिलता निर्धारित करना संभव है, आपको यह सुनिश्चित करने की ज़रूरत है कि आप कुछ अतिरिक्त काम नहीं शुरू करते हैं जो आपके विचार से अधिक लंबा होता है (जैसे भवन कार्य शुरू करने से पहले फ़ंक्शन के लिए सभी इनपुट)।
इसके अलावा आपको यह भी याद रखना होगा कि संभावित मूल्यों की एक बड़ी श्रृंखला को आजमाने में कितना समय लगेगा और यह कितना समय लगेगा, एक और यथार्थवादी परीक्षण केवल अपने कार्य को एक बड़े यथार्थवादी पर कॉल करना है ऊपरी बाउंड मान और निर्धारित करें कि इसका उपयोग समय आपके उपयोग के लिए पर्याप्त है या नहीं।
यदि आपको स्रोत कोड के बिना ब्लैक बॉक्स परीक्षण कर रहे हैं (और स्रोत को देखने के लिए परावर्तक जैसे कुछ का उपयोग नहीं कर सकते हैं), या यदि आपको पीएचबी साबित करना है कि कोडित एल्गोरिदम जितना तेज़ हो सकता है (स्थिरांक में सुधारों को अनदेखा कर रहा है), जैसा कि आप दावा करते हैं।
आम तौर पर आप नहीं कर सकते हैं, लेकिन हे, वे अभी भी माइक्रोसॉफ्ट विंडोज बेचते हैं और एयरक्राफ्ट और लाइफ सपोर्ट सिस्टम के लिए सॉफ्टवेयर लिखते हैं, जहां जटिलता आश्चर्यजनक है या नॉन-हॉलिंग अत्यधिक महत्व का है। –
यह गलत है। रोकथाम की समस्या बताती है कि यह निर्धारित करने के लिए कोई एल्गोरिदम नहीं है कि एक ट्यूरिंग-पूर्ण भाषा में एक मनमाना प्रोग्राम-इनपुट जोड़ी रुक जाएगी या नहीं। हालांकि, परिभाषा के अनुसार, एल्गोरिदम के कार्यान्वयन, चरणों की एक सीमित संख्या में पूरा होने की गारंटी है। – Nabb
@Nabb आप जो कहते हैं वह धारणा में सही है कि एल्गोरिदम कुछ इनपुट की अपेक्षा करता है जो पूर्वनिर्धारित आवश्यकताओं के सेट को पूरा करता है। एल्गोरिदम को किसी अन्य (अप्रत्याशित) इनपुट के लिए चरणों की सीमित संख्या में इसकी समाप्ति की गारंटी नहीं देनी पड़ती है। –