正如@emory指出的那样,证明自动确定任意一段代码的big-O时间复杂度是不可能的(证明是Halting
Problem的减少)。但是,有些工具可以尝试通过在几个不同的输入上运行来凭经验来测量代码的复杂性。Goldsmith,Aiken和Wilkerson的论文“测量经验计算复杂性”中描述了一种这样的工具。它通过尝试对程序的运行时间与其输入大小进行回归来工作。该工具称为
Trend-prof (已停产),可供参考。
希望这可以帮助!
欢迎分享,转载请注明来源:内存溢出
正如@emory指出的那样,证明自动确定任意一段代码的big-O时间复杂度是不可能的(证明是Halting
Problem的减少)。但是,有些工具可以尝试通过在几个不同的输入上运行来凭经验来测量代码的复杂性。Goldsmith,Aiken和Wilkerson的论文“测量经验计算复杂性”中描述了一种这样的工具。它通过尝试对程序的运行时间与其输入大小进行回归来工作。该工具称为
Trend-prof (已停产),可供参考。
希望这可以帮助!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)