Поиск сложности функций Haskell

Ответ 1

Вы можете вычислить только точную сложность функции, просмотрев код. Однако вы можете оценить его с помощью criterion.

Например, следующая программа оценивает сложность subsequence как функцию длины списка.

module Main where

import Criterion (bench, nf)
import Criterion.Main (defaultMain)
import Data.List (subsequences)
import Control.DeepSeq (deepseq)

main = defaultMain (map createBenchmark [0, 2 .. 24])
    where
        createBenchmark n =
            let
                xs = replicate n 'x'
            in
                xs `deepseq` (bench (show n) $ nf subsequences xs)

Если вы скомпилируете его (с помощью -O2!) и запустите его с помощью

./Main -u report

(или

./Main --csv report

в новых версиях критерия)

вы получите CSV файл с данными (среднее время, дисперсия и другая информация за каждый прогон).

Если вы построите эти данные, вы поймете, что они экспоненциальны в n, как показывает следующий сеанс gnuplot.

> f(x) = a * exp(b * x)
> fit f(x) 'report' using ($0 * 2):2 every ::2 via a,b
...

Final set of parameters            Asymptotic Standard Error
=======================            ==========================

a               = 1.7153e-07       +/- 5.441e-09    (3.172%)
b               = 0.711104         +/- 0.001438     (0.2023%)


correlation matrix of the fit parameters:

               a      b      
a               1.000 
b              -1.000  1.000
> set log y
> set xlabel 'n'
> set ylabel 'mean time [s]'
> plot 'report' using ($0 * 2):2 every ::2 with lp title 'data', f(x) title 'fit'

a приблизительно равен нулю, а b почти не имеет ошибки. Поэтому довольно уверенно предположить, что сложность O (2 ^ n), так как e ^ 0.71 почти ровно 2.

Конечно, этот метод предполагает, что вы фактически используете все, возвращаемое функцией. Если вы только получаете доступ к первому элементу возвращаемого списка, сложность будет равна O (1) из-за ленивой оценки.

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