假设我有一个需要logN + 1的内存的算法,其中N是问题的大小(要处理的位数)。我提出了第二个版本,将内存需求降低到(logN) / 2 + 1。我学到常量在大O分析中被忽略,因此两个算法版本的复杂度都为O(logN)。
现在,如果我计算使用第二个算法版本节省的内存,则会得到
保存在N = M(N)= 1-[(logN) / 2 + 1] / [logN + 1] lim N→∞ M(N)= 1/2
这表明渐近地,我总会节省50%的内存。我困惑的是为什么我无法在大O分析中看到这种收益?
我的第二个问题是:如果我关于大O符号的理解是错误的,那么突出第二个算法版本中所节省的内存的正确方法是什么?
现在,如果我计算使用第二个算法版本节省的内存,则会得到
保存在N = M(N)= 1-[(logN) / 2 + 1] / [logN + 1] lim N→∞ M(N)= 1/2
这表明渐近地,我总会节省50%的内存。我困惑的是为什么我无法在大O分析中看到这种收益?
我的第二个问题是:如果我关于大O符号的理解是错误的,那么突出第二个算法版本中所节省的内存的正确方法是什么?