Легко получить указание (например, «является ли функция линейной? Сублинейной? Полиномиальной? Экспоненциальной")
Трудно найти точную сложность.
Например, вот решение Python: вы предоставляете функцию и функцию, которая создает для нее параметры размера N. Вы получаете список (n, времени) значений для построения графика или для выполнения регрессионного анализа . Он умножается один раз на скорость, чтобы получить действительно хорошее указание, он должен был бы рассчитать его много раз, чтобы минимизировать влияние факторов окружающей среды (например, с помощью модуля timeit ).
import time
def measure_run_time(func, args):
start = time.time()
func(*args)
return time.time() - start
def plot_times(func, generate_args, plot_sequence):
return [
(n, measure_run_time(func, generate_args(n+1)))
for n in plot_sequence
]
И чтобы использовать его для сортировки по времени:
def bubble_sort(l):
for i in xrange(len(l)-1):
for j in xrange(len(l)-1-i):
if l[i+1] < l[i]:
l[i],l[i+1] = l[i+1],l[i]
import random
def gen_args_for_sort(list_length):
result = range(list_length) # list of 0..N-1
random.shuffle(result) # randomize order
# should return a tuple of arguments
return (result,)
# timing for N = 1000, 2000, ..., 5000
times = plot_times(bubble_sort, gen_args_for_sort, xrange(1000,6000,1000))
import pprint
pprint.pprint(times)
Это напечатано на моей машине:
[(1000, 0.078000068664550781),
(2000, 0.34400010108947754),
(3000, 0.7649998664855957),
(4000, 1.3440001010894775),
(5000, 2.1410000324249268)]