在树状结构csp问题的最坏情况下运行ac-3算法的复杂度是多少
发布网友
发布时间:2022-04-19 12:30
我来回答
共2个回答
热心网友
时间:2023-10-24 22:47
最差情况下的复杂度是所有可能的输入数据所消耗的最大资源,如果最差情况下的复杂度符合我们的要求,我们就可以保证所有的情况下都不会有问题。
某些算法经常遇到最差情况。比如一个查找算法,经常需要查找一个不存在的值。
也许你觉得平均情况下的复杂度更吸引你,可是平均情况也有几点问题。第一,难计算,多数算法的最差情况下的复杂度要比平均情况下的容易计算的多,第二,有很多算法的平均情况和最差情况的复杂度是一样的. 第三,什么才是真正的平均情况?如果你假设所有可能的输入数据出现的概率是一样的话,也是不合理的。其实多数情况是不一样的。而且输入数据的分布函数很可能是你没法知道。
考虑最好情况的复杂度更是没有意义。几乎所有的算法你都可以稍微修改一下,以获得很好的最好情况下的复杂度(要看输入数据的结构,可以是O(1))。怎样修改呢? 预先计算好某一输入的答案,在算法的开始部分判断输入,如果符合,给出答案。
热心网友
时间:2023-10-24 22:47
假设边N,每个节点值域大小最大为M,ac-3算法对于每条边都至多经历一遍。故为O(NM)