Roh*_*han 18 algorithm performance complexity-theory big-o
我刚读过Cormen的算法书,认为big-O和big-omega不遵循三分法属性.这意味着对于两个功能,f(n)并且g(n)可能是既不存在f(n) = O(g(n))也不f(n) = Omega(g(n))成立的情况.在例子中,他们认为如果功能n^(1+sin n)是可能的.
虽然它是正确的,但在现实世界算法中可能有类似的运行时间sin n.因为随着输入大小的增加,它有时会减少.有没有人知道任何这样的算法,或者可以提供一个小代码片段来做到这一点.
谢谢你的答案,所以在这种情况下假设给定一个大小为n的问题P是正确的,如果它不能通过任何已知的算法在O(f(n))时间内求解,那么P的下界是欧米茄(F(N)).
随着子句与变量的比率增加,随机生成的3CNF子句的SAT平均运行时间最终会下降.直觉是当相对于变量的数量有很多条款时,公式更可能"明显地"不可满足; 也就是说,典型的SAT求解算法(比穷举搜索更好的一步或两步,但足够简单以涵盖在本科逻辑课程中)很快就会达到矛盾并停止.
当然,这些是对"随机"3CNF公式的一些概念的实验观察.我不确定人们已经证明了什么.
我很难想象一个复杂性降低的有意义的问题。一个“有意义的”问题需要读取或触摸其所有输入的部分内容。除非输入以非常低效的方式编码，否则处理它应该花费越来越多的时间。
不过，它可能会逐渐增加到一个常数。