seo公司网站建设,WordPress防伪证书插件,快递网站怎么做的,住房和城乡建设部网站建筑合同问题#xff1a; 最近有好几学生问我#xff0c;无论是计算机算法概论、还是数据结构书中#xff0c; 关于算法的时间复杂度很多都用包含O(logN)这样的描述#xff0c;但是却没有明确说logN的底数究竟是多少。 解答#xff1a;
算法中log级别的时间复杂度都是由于使用了分…问题 最近有好几学生问我无论是计算机算法概论、还是数据结构书中 关于算法的时间复杂度很多都用包含O(logN)这样的描述但是却没有明确说logN的底数究竟是多少。 解答
算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。 如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然。 不过无论底数是什么,log级别的渐进意义是一样的。 也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。 我们先考虑O(logx(n))和O(logy(n))x!y我们是在考虑n趋于无穷的情况。 求当n趋于无穷大时logx(n)/logy(n)的极限可以发现极限等于lny/lnx也就是一个常数 也就是说在n趋于无穷大的时候这两个东西仅差一个常数。 所以从研究算法的角度log的底数不重要。 最后结合上面我也说一下关于大O的定义算法导论28页的定义 注意把这个定义和高等数学中的极限部分做比较 显然可以发现这里的定义正是体现了一个极限的思想 假设我们将n0取一个非常大的数字 显然当n大于n0的时候我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。 所以书上说写的Ologn已经可以表达所有底数的对数了就像O(n^2)一样。 没有非常严格的证明不过我觉得这样说比较好理解如果有兴趣证明完全可以参照高数上对极限趋于无穷的证明。
其实这里的底数对于研究程序运行效率不重要写代码时要考虑的是数据规模n对程序运行效率的影响常数部分则忽略同样的如果不同时间复杂度的倍数关系为常数那也可以近似认为两者为同一量级的时间复杂度。
现在来看看为什么底数具体为多少不重要
读者只需要掌握依稀记得中学数学知识就够了。 假设有底数为2和3的两个对数函数如上图。当X取N数据规模时求所对应的时间复杂度得比值即对数函数对应的y值用来衡量对数底数对时间复杂度的影响。
比值为log2 N / log3 N运用换底公式后得(lnN/ln2) / (lnN/ln3) ln3 / ln2ln为自然对数显然这三个常数与变量N无关。
用文字表述算法时间复杂度为logn时不同底数对应的时间复杂度的倍数关系为常数不会随着底数的不同而不同因此可以将不同底数的对数函数所代表的时间复杂度当作是同一类复杂度处理即抽象成一类问题。
当然这里的底数2和3可以用a和b替代ab大于等于2属于整数。a,b取值是如何确定的呢
有点编程经验的都知道分而治之的概念。排序算法中有一个叫做“归并排序”或者“合并排序”的算法它用到的就是分而治之的思想而它的时间复杂度就是N*logN此算法采用的是二分法所以可以认为对应的对数函数底数为2也有可能是三分法底数为3以此类推。但是不可能我分数及负数。
说明为了便于说明本文时间复杂度一概省略 O 符号。
