Queste funzioni Python non hanno tempi di funzionamento come previsto

Question

(Non sono sicuro che questa domanda appartenga a questo forum o CS. L'ho mantenuta qui perché ha codice specifico per Python. Effettua la migrazione se necessario!) I'm studiare algoritmi in questi giorni, usando Python come mio strumento di scelta. Oggi, volevo tracciare i tempi di esecuzione di tre variazioni di un problema semplice: calcolare la media prefissata di una data sequenza (lista).

Qui ci sono le tre varianti:

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') 

Così Sto raccogliendo i tempi di esecuzione dei tre algoritmi e li stampa. I miei dati finale si presentava così:

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 

Quando tracciato, questi numeri si traducono in:

Ora, secondo il libro di testo che sto seguendo, le funzioni e quadsumm si suppone eseguire in tempo quadratico, mentre prev verrà eseguito in tempo lineare. Posso vedere che prev è significativamente più veloce di quad e leggermente più veloce di summ, ma tutte queste mi sembrano funzioni lineari! Inoltre, c'è uno spaventoso scarto tra summ e prev.

Qualcuno potrebbe spiegare cosa c'è che non va?

Answer 1

La complessità asintotica di un algoritmo indica la sua dipendenza dalla lunghezza dell'input. Qui, non si modifica la dimensione di ingresso tra le esecuzioni, basta cambiare il numero di volte per eseguire ogni algoritmo (come un parametro a 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)) 

Per ottenere valido confronto, di modificare la lunghezza della sequenza tra piste.