找到Haskell功能的复杂性

Question

我如何找到复杂性（以 big-o ）？

例如， ？

Answer 1

您只能通过查看代码来计算功能的确切复杂性。但是，您可以使用 criterion 来估算它。

例如，以下程序估算子序列的复杂性作为列表长度的函数。

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

在较新版本的Criteron中运行），

您将获得带有数据的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之外什么都不使用）。