如果有两个算法可以计算出相同的结果,但时间复杂度不同,那么O(log n)是始终更快的吗?如果是,请解释一下。顺便说一句,这不是一个作业问题。
不是的。如果一个算法在 N/100
的时间内运行,而另一个算法在 (log N)*100
的时间内运行,则对于较小的输入大小,第二个算法将更慢。渐近复杂度关注的是当输入大小趋向无穷时,运行时间的行为。
对于大小为n的输入,O(n)算法将执行与n成比例的步骤,而O(log(n))算法将执行大约log(n)的步骤。
显然,log(n)比n小,因此复杂度为O(log(n))的算法更好。因为它会快得多。