इन पायथन कार्यों में

Question

(मुझे यकीन नहीं है कि यह प्रश्न यहां है या सीएस मंच है। मुझे यह नहीं पता है क्योंकि इसमें पाइथन-विशिष्ट कोड है। कृपया आवश्यकता होने पर माइग्रेट करें!) मैं पसंद के मेरे उपकरण के रूप में पाइथन का उपयोग करते हुए, इन दिनों एल्गोरिदम का अध्ययन करना। आज, मैं चलने वाले समय को एक साधारण समस्या के तीन भिन्नताओं को साजिश करना चाहता था: दिए गए अनुक्रम (सूची) के उपसर्ग औसत की गणना करें।

import timeit 

seq = [20, 45, 45, 40, 12, 48, 67, 90, 0, 56, 12, 45, 67, 45, 34, 32, 20] 

# Quadratic running time 
def quad (S): 
    n = len(S) 
    A = [0] * n 

    for j in range(n): 
     total = 0 
     for i in range(j+1): 
      total += S[i] 
     A[j] = total/(j+1) 

    return A 

# Use prev result 
def prev (S): 
    n = len(S) 
    A = [0] * n 

    for j in range(n): 
     if j == 0: 
      A[j] = S[j] 
     else: 
      A[j] = (A[j-1]*j + S[j])/(j+1) 
    return A 

# Use Python's sum method 
def summ (S): 
    n = len(S) 
    A = [0] * n 

    for j in range(n): 
     A[j] = sum(S[0:j+1])/(j+1) 
    return A 

def plot_func (name): 
    for i in range(0, 1000000, 100000): 
     t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name)) 
     print(i, ',', t.timeit(number=i)) 

plot_func('quad') 
plot_func('prev') 
plot_func('summ') 

तो मैं तीन एल्गोरिदम के चलने वाले समयों का संग्रह कर रहा हूँ और उन्हें साजिश रचने:

यहाँ तीन विविधताएं हैं।

Input size Quadratic Prev Summ 
(x100000) 
1 4.92E-007 7.78E-007 3.47E-007 
2 1.582717351 0.603501161 0.750457885 
3 3.205707528 1.176623609 1.508853766 
4 4.796092943 1.76059924 2.295842737 
5 6.457349465 2.34945291 3.112500982 
6 8.057410897 2.947556047 3.882303307 
7 9.59740446 3.520847787 4.654968896 
8 11.36328988 4.122617632 5.412608518 
9 12.776150393 4.703240974 6.181500295 
10 14.704703677 5.282404892 6.882074295 

जब साजिश रची, इन नंबरों का परिणाम:: मेरा अंतिम डेटा इस तरह देखा,

अब पाठ्यपुस्तक मेरा अनुसरण कर के अनुसार, कार्यों quad और summ करने वाले हैं वर्गबद्ध समय में चलाएं, जबकि prev रैखिक समय में भाग लेंगे। मैं देख सकता हूं कि prevquad से काफी तेज है और summ से कुछ हद तक तेज़ है, लेकिन ये सभी मेरे लिए रैखिक कार्यों की तरह दिखते हैं! इसके अलावा, summ और prev में भयभीत रूप से थोड़ा अंतर है।

क्या कोई बता सकता है कि क्या गलत है?

Answer 1

एल्गोरिदम की एसिम्प्टोटिक जटिलता का अर्थ इनपुट लंबाई से इसकी निर्भरता है। यहाँ, आप रन के बीच इनपुट आकार में परिवर्तन नहीं करते, तो आप सिर्फ बार प्रत्येक एल्गोरिथ्म चलाने के लिए की संख्या में परिवर्तन (timeit() के लिए एक पैरामीटर के रूप में):

for i in range(0, 1000000, 100000): 
     t = timeit.Timer('{}(seq)'.format(name), 'from __main__ import {}, seq'.format(name)) 
     print(i, ',', t.timeit(number=i)) 

उचित तुलना करने के लिए, के बीच अपने अनुक्रम की लंबाई को बदल रन।