Andy Melnikov (nponeccop) wrote,
Andy Melnikov

Сложность ленивых алгоритмов - литература

Complexity Analysis for a Lazy Higher-Order Language (1990) by David Sands

We concentrate here on the construction of equations which compute the time-complexity of expressions in a lazy higher-order language. The problem with higher-order functions is that complexity is dependent on the cost of applying functional parameters. Structures called cost-closures are introduced to allow us to model both functional parameters and the cost of their application. The problem with laziness is that complexity is dependent on context. Projections are used to characterise the context in which an expression is evaluated, and cost-equations are parameterised by this context-description to give a compositional time-analysis.

Нашел, вероятно, по ссылкам из диссертации Окасаки. Довольно неинтересная статья - полезна только как обзор сложностей оценки сложности, возникающих из-за ленивости и функций высших порядков.

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.