【算法设计与分析】05 有关函数的渐进的界的定理

雨点打透心脏的1/2处 2024-04-18 23:59 59阅读 0赞

> 上一篇文章学习了函数的渐近的界定义，本篇文章继续学习函数渐近的界定理。这些定理的证明，用到了函数渐近的界的定义。点击查看上一篇文章：[【算法设计与分析】04 函数的渐进的界][04]

### 文章目录 ###

*   *  1. 定理1
     *   *  1.1 证明定理1
         *  1.2 估计函数的阶
         *  1.3 一些重要的结论
         *   *  1.31 多项式函数的阶低于指数函数的阶
             *  1.32 对数函数的阶低于幂函数的阶
     *  2. 定理2
     *   *  2.1 例子
     *  3. 定理3
     *  4. 总结

## 1. 定理1 ##

定理： 设 f 和 g是定义域为自然数集合的函数.  
![在这里插入图片描述][20190914185445764.png_pic_center]

### 1.1 证明定理1 ###

![在这里插入图片描述][20190914185922610.png]

### 1.2 估计函数的阶 ###

![在这里插入图片描述][20190914190108173.png]

### 1.3 一些重要的结论 ###

#### 1.31 多项式函数的阶低于指数函数的阶 ####

可证明：多项式函数的阶低于指数函数的阶

![在这里插入图片描述][2019091419032997.png_pic_center]

证 不妨设d为正整数，

![在这里插入图片描述][20190914190420853.png]

#### 1.32 对数函数的阶低于幂函数的阶 ####

可证明：对数函数的阶低于幂函数的阶

![在这里插入图片描述][20190914190521918.png_pic_center]  
证明：  
![在这里插入图片描述][20190914190545451.png_pic_center]

## 2. 定理2 ##

定理 设函数f, g, h的定义域为自然数集合，

![在这里插入图片描述][20190914210005498.png]  
函数的阶之间的关系具有传递性

### 2.1 例子 ###

按照阶从高到低排序以下函数：

![在这里插入图片描述][2019091421023332.png]

排序 h(n), f(n), g(n), t(n)

## 3. 定理3 ##

定理 假设函数f 和g的定义域为自然数集，若对某个其它函数 h, 有

f =O(h) 和 g=O(h)，

那么 f + g = O(h).

该性质可以推广到有限个函数.

算法由有限个步骤组成，若每一步的时间复杂度函数的上届都是h(n),那么该算法的时间复杂度函数可以写成O(h(n)).

## 4. 总结 ##

1.  估计函数的阶的方法

*  计算极限
 *  阶具有传递性

1.  对数函数的阶低于幂函数的阶，多项式函数的阶低于指数函数的阶
2.  算法的时间复杂度是各步骤操作时间之和，在常数步的情况下，取最高阶的函数即可。

[04]: https://blog.csdn.net/qq_37375427/article/details/94150310
[20190914185445764.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/6021f168a2a6445a9193147e5f8e0ce0.png
[20190914185922610.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/dadc26e246704bd29f63eaae00985622.png
[20190914190108173.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/58363c52679740cfa4c7b3a9148f1c3c.png
[2019091419032997.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/40b32444995349ec901057c27db2ae2e.png
[20190914190420853.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fdbd71b181ab426fa8108b1410341cae.png
[20190914190521918.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/00429dfd81524bf0b07c0b40c31b1518.png
[20190914190545451.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f644f042cdb24493a23818fc807ce466.png
[20190914210005498.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/698187e4f8be45e8a4e095f13da63f95.png
[2019091421023332.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/678885889acf42e6b6a27d4e848dc153.png