Notations

通过查看函数内部的循环嵌套级别，静态估计给定Python函数的渐近符号。

这是一个早期原型

示例

from notations import notation

def my_example_function(arg1, arg2):
    f = 0
    for a in arg1:
        for i in a:
            f+=1
    for b in arg2:
        for j in b:
            f+=1

print(notation(my_example_function))

将打印 Θ(n^2)

有关更多示例，请参阅 test_notations.py。

待办事项

这是目前一个概念的大致草图。

• while 运算符
• 查看函数中输入参数之间的关系，仅仅因为循环嵌套，并不意味着 O(n_n) 是正确的
• 循环内的分支
• 测试生成器

常见问题解答

• 为什么不使用AST? AST不能在运行时（容易地）从代码对象构建，此库旨在用于评估编译函数的执行顺序。
• 如何在不运行代码的情况下计算顺序? 此函数通过查看函数中的循环嵌套级别，使用生成器和参数之间的关系来确定顺序。动态运行时基准测试容易受到环境条件（嘈杂的邻居）的影响，并且已经有大量工具可以做到这一点。

研究笔记

• 关于渐近层的论文
• 关于theta、O和omega函数的笔记

变更

0.2.0

• 修改了 repr 的theta值

0.1.0

• 支持基本for循环的初始原型