- 译者:cdpath 译者
- 校对者:zaraguo(扎拉古)与 whatbeg(秋胡)
了解算法的复杂度是基础,而掌握其背后的原理则是更进一步的要求。
无论您是计算机专业出身,还是希望有效解决优化问题,要利用自己的知识解决实际问题,理解时间复杂度是必不可少的。
先从直观的O(1)和O(n)复杂度说起。O(1)表示一次操作即可直接获取目标元素(如字典或哈希表),而O(n)意味着需要检查n个元素来寻找目标。那么,O(log n)又是什么意思呢?
初次听到O(log n)时间复杂度,您可能是在学习二分搜索算法时。二分搜索因其特定行为而具有log n的时间复杂度。让我们来看看二分搜索是如何实现的。
尽管在最佳情况下二分搜索的时间复杂度为O(1),但在最坏的情况下(或平均情况),其时间复杂度为O(log n)。我们以最坏情况为例进行说明。假设有一个包含16个元素的有序数组。
以寻找数字13为例。
这个有序数组共有十六个元素。
我们选择中间元素作为中心点(即数组长度的一半)。
如果13小于中心点值,则无需考虑数组的后半部分。
重复这个过程,每次选择子数组的中间元素进行比较。
每次比较都会使搜索范围减半。
为了在包含16个元素的数组中找到目标元素,我们需要将数组平均分割四次。换句话说,
简化后的公式表示为...
对于n个元素的情况,可以类推...
将分子和分母代入指数中...
等式两边同时乘以2的k次方...
最终得出的结果是...
现在来谈谈“对数”的定义:对数表示为了使某个数(底数)等于给定数,必须连续乘以自己的次数。换句话说,它可以表示为这种形式...
对数形式具体为...
log n确实是有意义的,不是吗?没有其他方式能更准确地描述这种行为。