老师,上篇文章问的问题,你没有回答我,我又看了几遍还是不明白。希望看到给我解答一下。
上篇均摊时间复杂度 insert 那个例子用加权时间复杂度分析。 1 * 1 / ( n + 1 ) + 1 * 1 / ( n + 1 ) + … + 1 * 1 / ( n + 1 ) + n * 1 / ( n + 1 )= O ( 1 )这个公式怎么推出来等于 O ( 1 )的。按照我的理解 n 个 1 / ( n + 1 )相加再与 n / ( n + 1 )相加应该是 2n / ( n + 1 )才对。而这个结果也化不成 O (1) 呀。我真的是百思不得其解。还请老师帮忙解答下,谢谢!
作者回复: 不好意思 留言太多 有时候就淹没了 实在抱歉
即便是你说的2n/(n+1) 那分子和分母是相同量级的。如果我们忽略分母的1 就简化为2n除以n。就等于2。复杂度上讲过常量级的都可以表示为O(1)