对数是求幂的逆运算。取幂的一个示例是在每个步骤中将项目数量加倍。因此，对数算法通常将每个步骤的项目数量减半。例如，二进制搜索属于该类别。
许多算法需要大步数的对数，但是每个大步幅都需要O（n）个工作单元。Mergesort属于这一类。
通常，您可以通过将它们可视化为平衡的二叉树来识别这些类型的问题。例如，这是合并排序：
6 2 0 4 1 3 7 5 2 6 0 4 1 3 5 7 0 2 4 6 1 3 5 7 0 1 2 3 4 5 6 7
输入的最上方是树的叶子。该算法通过对上面的两个节点进行排序来创建一个新节点。我们知道平衡二叉树的高度为O（log n），所以有O（log
n）个大步。但是，创建每个新行需要O（n）的工作。O（n）的O（log n）大步骤每个都意味着mergesort总体上为O（n log n）。
通常，O（log n）算法看起来像下面的函数。他们在每一步都会丢弃一半的数据。
def function(data, n): if n <= constant: return do_simple_case(data, n) if some_condition(): function(data[:n/2], n / 2) # Recurse on first half of data else: function(data[n/2:], n - n / 2) # Recurse on second half of data
O（n log n）算法看起来像下面的函数。他们还将数据分成两半，但需要同时考虑这两个部分。
def function(data, n): if n <= constant: return do_simple_case(data, n) part1 = function(data[n/2:], n / 2) # Recurse on first half of data part2 = function(data[:n/2], n - n / 2) # Recurse on second half of data return combine(part1, part2)
其中do_simple_case（）花费O（1）的时间，而Combine（）花费不超过O（n）的时间。
该算法不需要将数据精确地分成两半。他们可以将其分为三分之一和三分之二，那很好。对于平均情况下的性能，将其平均拆分为一半就足够了（例如QuickSort）。只要对（n/某物）和（n-n /某物）进行递归，就可以了。如果将其分解为（k）和（nk），则树的高度将为O（n）而不是O（log n）。
