Как я могу оценить рост функции?

Question

Предположим, что у меня есть эта информация:

N seconds 

    216  0.00 
1296  0.48 
7776  89.73 
46656 16480.96 

Как я могу оценить рост этой функции ??

Что такое эмпирический порядок роста?

Как я могу оценить эмпирический порядок роста?

Любая помощь будет оценена!

Answer 1

Один из способов - создать график для всех точек данных, которые у вас есть, с помощью любого программного обеспечения для работы с электронными таблицами (например, Excel). График N vs Seconds даст вам хорошую оценку того, как увеличивается время (секунды) с увеличением размера ввода (N), предоставляя вам информацию о том, имеет ли он линейный рост или экспоненциальный рост или что-то еще. Требование здесь состоит в том, что у вас должно быть достаточно данных, чтобы быть достаточно уверенным в наблюдаемом росте.

Теперь в случае, если у вас есть доступ к коду методы вы можете пройти через код и посмотреть на его сложность, которая будет является четким представлением о его росте

Answer 2

Plotting данных является хорошим началом; если вы рисуете его по линейным шкалам, а также по логарифмическим шкалам, вы можете отличить функцию роста полинома от функции экспоненциального роста.

Для быстрой оценки порядка сложности вычислите коэффициенты увеличения времени. Из команды

dc -e '46656 7776/ 16480.96 89.73/ 7776 1296/ 89.73 0.48/f' 

который выводит

186 
6 
183 
6 

или команду питона

python -c 'print 46656/7776, 16481/90, 7776/1296, 90/0.48' 

, который выводит

6 183 6 187.5 

один видит, что по мере увеличения размера проблемы с коэффициентом из шести, исполнение время увеличивается более чем в 180 раз, что эмпирически указывает на сложность O (n³). (An empirical находка один на основе наблюдений, а не теории. Подгонка кривой к функции черного ящика, где нет никакой информации о процессе, просто знание входов и выходов, является эмпирическим.)

В более общем плане, a multiple regression пакет может использоваться для изучения возможных функций подгонки кривой. Предположим, что x - это вход, и y = f (x) наблюдаемый выход. Идея в множественной регрессии состоит в вычислении дополнительных входных значений, таких как x², x³, ln x, x · (ln x), и т. Д., А затем найти наилучшее соответствие для y, которое представляет собой линейную комбинацию входных значений ,

В грубом приближении, можно также написать программу, которая вычисляет коэффициенты г/г (х) для выполнения различных функций г и для каждого х, у пары значений.Ниже приведен пример этого метода применяется к данным, показанным на вопрос:

import math 
Ns=(216,1296,7776,46656) 
times=(0.00,0.48,89.73,16480.96) 
for x,y in zip(Ns,times): 
    print '{:5} {:8.2f} {:8.2} {:10.3} {:10.3} {:10.3} {:10.3}'.format(x, y, y/x, y/x**2, y/x**3, y/(x**2.92), y/(x**2 * math.log(x)**8)) 

, который производит

216  0.00  0.0  0.0  0.0  0.0  0.0 
1296  0.48 0.00037 2.86e-07 2.21e-10 3.91e-10 4.11e-14 
7776 89.73 0.012 1.48e-06 1.91e-10 3.91e-10 3.58e-14 
46656 16480.96  0.35 7.57e-06 1.62e-10 3.84e-10 4.24e-14 

Последние две функции в указанной выше программы питона, т.е. г (х) = х ^2.92 и g (x) = x² · (ln x) ⁸, включены для иллюстрации того, что вы можете протестировать довольно сложные функции. Но обратите внимание, что этот метод несколько ad hoc.