gpt4 book ai didi

估计另一个算法的时间复杂度的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:49:06 26 4
gpt4 key购买 nike

是否可以开发一种算法来估计另一种算法的时间复杂度?我的意思是,输入是某种算法,输出可能是它的时间复杂度(Big-Oh、Big-Omega 等等)。我在网上找不到任何相关信息。

谢谢

最佳答案

让我稍微扩展一下@interjay 的评论。

halting problem在问

if it possible to design a Turing Machine (you may think it as an program in you computer) such that given a Turing Machine (again, think it as a program) it can decide whether or not this input Turing Machine will terminate eventually.

可以证明设计这样的图灵机是不可能的。现在让我们考虑你的问题,如果你能够设计一个算法想要,您将能够回答给定的图灵机是否会终止。不幸的是,这是不可能的。

上述论点称为“归约”,这是表明给定问题无法解决的最流行方式之一。

关于估计另一个算法的时间复杂度的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33462482/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com