temps et l'espace complexité de la liste à la conversion str en Python

Question

Essayer de savoir quelle est la complexité du temps de coulée à chaîne

str([1,2,6,...,3,6]) 

sûr qu'il est O (1) Je ne sais pas comment vérifier. À propos de la complexité de l'espace, Cela ne devrait pas être linéaire à la liste de taille, penser O (1), car la chaîne a une taille maximale.

Answer 1

Hypothesis

str conversion d'une liste est constante dans la complexité.

---

Expérience

Créer des listes de différentes tailles:

In [67]: list10 = np.random.choice(100, 10).tolist() 

In [68]: list100 = np.random.choice(100, 100).tolist() 

In [69]: list10000 = np.random.choice(100, 10000).tolist() 

In [70]: list1000000 = np.random.choice(100, 1000000).tolist() 

---

Observation

Utilisez timeit et le temps convers sur le processus de chaque liste:

In [71]: %timeit str(list10) 
1000000 loops, best of 3: 1.69 µs per loop 

In [72]: %timeit str(list100) 
100000 loops, best of 3: 10.6 µs per loop 

In [73]: %timeit str(list10000) 
1000 loops, best of 3: 958 µs per loop 

In [74]: %timeit str(list1000000) 
10 loops, best of 3: 96.8 ms per loop 

---

Conclusion

Hypothesis est incorrect. La conversion est linéaire dans le temps.