O(lgn)是什么意思？

Question

老师，我数学不太好， 函数的底数是几应该没有意义吧？

我是想代入实际数字计算一下，比如有 256 个元素：

O(n^2) = 256 * 256 = 65636
O(nlogn) = 256 * 8 = 2048

(lgn) 是什么意思 ， 是以10为底n的对数 ？ 还是说是logn的缩写？

如果是前者 ：(以10为底)
O(lgn) = 2.4082399653
如果是后者 ：(都以2为底)
O(lgn) = 8

说到这里，我想表达的是，O(lgn）是真快呀，比(nlogn)快了几百倍呀。

Answer 1

liuyubobobo 2020-02-22 17:00:17

在计算机的世界中，通常是以 2 为底的。因为在计算机的世界中，通常会二分，比如二分查找法，二叉树等。但并不绝对。比如这个课程后续学习 Trie，就是一个 26 叉树：）

但是，其实，对于复杂度分析来说，以多少为底并不重要，就像 O(2n) 和 O(3n) 和 O(10000n) 都是 O(n) 一样，对于 logn 级别的复杂度，以多少为底，都被称为对数级别的复杂度：）

是的。O(logn) 是非常快的一种复杂度：）

继续加油！：）

• 提问者 sea_World #1

  老师回复真快呀。我刚才最后一句话不太严谨，用曲线图来看会更加直观。应该说，对于不同级别的复杂度，数据量越大时，差距就会越明显对吧？

• liuyubobobo 回复 提问者 sea_World #2

  是的。复杂度本身体现的就是当数据规模无穷大的时候，性能的变化趋势：）