uba*_*abd 5 algorithm math big-o
假设我有一个内存要求为logN + 1的算法,其中N是问题的大小(要处理的位数).我建议第二个版本将此内存需求减少到(logN)/ 2 + 1.我已经了解到在Big-O分析中忽略了常量,因此算法版本都具有O(logN)的复杂性.
现在,如果我计算使用算法的第二版保存的内存,我得到
记忆保存在N = M(N)= 1 - [(logN)/ 2 + 1]/[logN + 1]
lim N→∞M(N)= 1/2
这表明渐渐地我将永远保存50%的内存.我很困惑为什么我无法在Big-O分析中看到这种收益？
我的第二个问题是:如果我对Big-O表示法的理解是错误的,那么突出显示第二版算法中保存的内存的正确方法是什么？
请记住,大O符号不包括常数因子.函数f(n)= n和g(n)= 10 100 n都是O(n),尽管f(n)是比g(n)小得多的函数.
您的分析是正确的 - 如果您可以使用空间(log n)/ 2 - 1,那么您将(在极限范围内)将所需的内存量减半.然而,这不会出现在大O分析中,因为大O忽略了常数因素.正如其他一些答案中所提到的,big-O表示法捕获了长期增长率,虽然常数可能会告诉您更多关于所用空间的绝对数量,但常数并不能控制空间使用的长期增长率.
如果您想进行更精确的分析,可以在之前和之后给出确切的内存使用,然后说您已将内存使用量减少了50%.关于算法和数据结构的许多论文确实包含了常数因素,并提到它们正在获得恒定的加速.例如,Cholesky分解算法和高斯消元都给出了用于求解线性系统的O(n 3)算法,但是当可以使用Cholesky分解时,它可以减少约50%的运算.大多数涵盖这些主题的教科书都会提到虽然两种算法都是O(n 3),但前者在可以使用时优于后者.
希望这可以帮助!