二叉树的大 O 表示法

Question

我的教科书说在二叉树中查找节点的大 O 表示法是 O(log ₂ N)，如果N = 1那么 log ₂ N 将是 0，这是不可能的？这只是四舍五入1还是还有更多？

Answer 1

Big-O 表示法旨在描述当数据量（或任何N描述的内容）向无穷大增加时算法的执行时间（或内存消耗，或...）如何扩展。它并不意味着在给定特定值时提供精确的运行时间N。值较低时N，常数因子无论如何都会占主导地位。在这种情况下，您要推导出的只是此特定算法的执行时间以对数方式缩放。