找到Haskell函数的复杂性

Question

如何找到不同Haskell函数的复杂性(就big-O而言)？

例如,复杂性是subsequences多少？

Answer 1

您只能通过查看代码来计算函数的确切复杂性.但是,您可以使用标准估算它.

例如,以下程序估计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).