Complexité pratique contre complexité théorique

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche


Principe de la complexité

Etudes d'algorithmes

import timeit
def chronoquick(tab,nessais):
    '''Entrées: un tableau et un entier, Sortie: un entier''' 
    res = timeit.timeit("quickselectmed("+ str (tab)+")","from __main__ import quickselectmed" , number= nessais)
    return res

dichotomie

tri de tableau: main/python

Bulle500.PNG Python500.PNG

mediane

medianes des medianes, quickselect

Multiplication naive / Karatsuba