Logarithmic-time

释义 Definition

对数时间（复杂度）：指算法的运行时间随输入规模 \(n\) 增长而按对数增长，常写作 \(O(\log n)\)。在输入规模变大时，增长非常缓慢（例如常见于二分查找、平衡树操作等）。

例句 Examples

A binary search runs in logarithmic-time.
二分查找以对数时间运行。

With a balanced tree index, each lookup stays logarithmic-time even as the dataset grows to millions of records.
使用平衡树索引后，即使数据集增长到数百万条记录，每次查询仍能保持对数时间。

发音 Pronunciation (IPA)

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

词源 Etymology

logarithmic 来自 logarithm（对数）+ -ic（形容词后缀）；而 logarithm 源自希腊语词根，常解释为 logos（比例/理性） 与 arithmos（数） 的组合，表示一种与“数的比例关系”相关的计算概念。time 在计算机科学语境中指“运行时间/时间复杂度”，因此 logarithmic-time 直译就是“对数级的运行时间”。

相关词 Related Words

• Algorithm
• Complexity
• Big-o
• Logarithm
• Binary-search
• Balanced-tree
• Divide-and-conquer

文学与经典著作 Literary Works

• Introduction to Algorithms（《算法导论》，Cormen / Leiserson / Rivest / Stein）中在分析二分查找、堆与平衡结构时常用到 logarithmic time / O(log n) 的表述。
• The Art of Computer Programming（《计算机程序设计艺术》，Donald Knuth）在讨论查找、排序与数据结构分析时频繁涉及对数级增长与 \(O(\log n)\)。
• Algorithms（《算法》, Robert Sedgewick & Kevin Wayne）在讲解符号表、二叉查找树与平衡树时大量出现“对数时间”的复杂度描述。