Var*_*lyn 16 algorithm complexity-theory
如果有2个algorthim计算具有不同复杂性的相同结果,那么O(log n)总是会更快吗？如果是这样请解释.顺便说一句,这不是一个任务问题.
a3n*_*3nm 28
不可以.如果一个算法运行N/100而另一个算法运行(log N)*100,那么第二个算法对于较小的输入大小将会更慢.随着输入大小变为无穷大,渐近复杂性与运行时间的行为有关.
Ale*_*x D 17
不,它不会总是更快.但是,随着问题规模越来越大,最终您将始终达到O(log n)算法比O(n)算法更快的点.
在实际情况中,通常O(log n)算法将超过O(n)算法的点将非常快.O(log n)和O(n)之间存在很大差异,就像O(n)和O(n ^ 2)之间存在很大差异一样.
如果你有机会阅读Jon Bentley 撰写的编程珍珠,那里有一个很棒的章节,在那里他针对O(n ^ 2)算法进行O(n)算法,尽一切可能给出O(n ^ 2) ) 优势.(他用Alpha编码C中的O(n ^ 2)算法,用旧Z80或其他东西解释BASIC中的O(n)算法,运行频率约为1MHz.)令人惊讶的是O(n)的速度有多快算法超过O(n ^ 2).
但有时候,您可能会发现一种非常复杂的算法,其复杂性略好于简单算法.在这种情况下,不要盲目地选择具有更好的大O的算法 - 你可能会发现在极大的问题上它只会更快.