Logarithmic Time

释义 Definition

对数时间：指算法的运行时间随输入规模 (n) 增长得很慢，通常记为 **(O(\log n))**。常见于每次操作都能把问题规模“减半/按比例缩小”的过程（如二分查找、平衡二叉搜索树的查找/插入）。

发音 Pronunciation (IPA)

/ˌlɑːɡəˈrɪðmɪk taɪm/

例句 Examples

Binary search runs in logarithmic time on a sorted array.
二分查找在有序数组上以对数时间运行。

Because the tree stays balanced, each lookup takes logarithmic time even as the dataset grows to millions of records.
由于树保持平衡，即使数据增长到数百万条记录，每次查找仍只需要对数时间。

词源 Etymology

logarithmic 来自 logarithm（对数），而 logarithm 源于希腊语成分：logos（比例、计算）+ arithmos（数）。在计算机科学中，“logarithmic time” 用来强调：复杂度随规模增长呈“对数级”，增长速度远慢于线性时间。

相关词 Related Words

• Algorithm
• Complexity
• Big-O
• Binary
• Search
• Balanced
• Tree
• Divide-and-conquer
• Logarithm
• Efficiency

文学与作品 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）中广泛使用 “logarithmic time” 描述二分查找、堆、平衡树等操作的复杂度。
• The Art of Computer Programming（Donald E. Knuth，《计算机程序设计艺术》）在讨论算法分析与增长阶时涉及对数级时间/对数项。
• Algorithms（Robert Sedgewick & Kevin Wayne，《算法》）中常用该术语讲解查找、排序与符号表操作的效率。