sha*_*kin 2 algorithm big-o estimation
如果我有一个由(比方说)三个子算法组成的算法,所有子算法都具有不同的O()特性,例如:
我如何从理论上估计整个算法的O()？即不计时或执行任何其他实际测量.
有一个众所周知的配方或程序吗？
有一个众所周知的配方或程序吗？
既然那是基础数学,是的.但是在你的情况下甚至更简单:因为所有这些都给出了上限,你可以简单地取所有边界的最大值来获得总上限.
- 假设所有这些算法都是链接的(而不是嵌套的).如果算法是嵌套的,则需要将它们的上限相乘(在最简单的情况下).
为了说明,假设您有一个容器数据结构,其成本为O(log n),用于查找单个元素.您还有一个需要这样查找的算法,但运行时间为O(n)本身,假设查找成本不变,并且在输入上使用单个循环,每个循环具有恒定数量的查找.
现在,如果您想使用此算法的前面提到的容器数据结构,它的查找运行时显然会取代(假定的)常量时间查找.所以我们有相同的循环,但它的每个迭代现在需要O(log n)而不是常数时间O(1),因此整个运行时变为O(n log n).
| 归档时间： |
|
| 查看次数： |
5035 次 |
| 最近记录： |