【算法设计与分析】06 几类重要的函数

今天药忘吃喽~ 2024-04-19 06:01 56阅读 0赞

> 本篇文章中会用到上一篇文章的定理：[【算法设计与分析】05 有关函数的渐进的界的定理][05]
> 
> 主要学习常见的一些函数的阶

## 1. 基本函数类 ##

以下按阶的高低排序：

*  至少指数级： 2n, 3n, n!, …
 *  多项式级： n, n2, nlogn, n1/2, …
 *  对数多项式级： logn, log2n, loglogn, …

### 1.1 对数函数 ###

算法中常用的符号：  
![在这里插入图片描述][2019091423435044.png_pic_center]

性质：

![在这里插入图片描述][20190914234426877.png_pic_center]  
下面对上面的性质进行证明：

*  性质（1）证明

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

根据上一篇文章的内容，根据定理：logkn =  Θ \\Theta Θ ( logl n)

*  性质（2）（3）的证明

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

### 1.2 指数函数与阶乘 ###

#### 1.21 Stirling公式 ####

![在这里插入图片描述][20190914235326406.png_pic_center]  
利用这个公式可以求解出投资问题的搜索空间的大小（见前面的文章：[【算法设计与分析】01 算法涉及的研究内容概述][01]）

如下：

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

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

#### 1.22 log(n!) =  Θ \\Theta Θ (nlogn)的证明 ####

*  log(n!) = Ω (nlogn)的证明  
    ![在这里插入图片描述][20190915000627922.png]
 *  log(n!) = O(nlogn)的证明

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

### 1.3 取整函数 ###

*  下面是取整函数的一些性质，证明过程略

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

## 2 一些函数的阶的排序 ##

*  对下面的各个函数进行阶从大到小的顺序重新排序：  
    ![在这里插入图片描述][20190915000926792.png]
 *  排序后

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

## 3 总结 ##

本节简单的学习了几类常用函数的阶的性质，包括对数函数、指数函数、阶乘函数、取整函数

[05]: https://blog.csdn.net/qq_37375427/article/details/100833140
[2019091423435044.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8bbc924d6ee54c03912f5f1659d29c04.png
[20190914234426877.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d1b3c9f105ed497fa6a407e0afc454f5.png
[20190914234731336.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/f52ace9700544c49bce8dd650ad9abd4.png
[20190914235217837.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8bce0a467d1c4719970d40ba1f37b7f8.png
[20190914235326406.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/32823e37cc3341e2a2782c2860750951.png
[01]: https://blog.csdn.net/qq_37375427/article/details/93692946#23__140
[20190915000117389.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0cd09ea967ed4646846744cd1ea85989.png
[20190915000136498.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7b1935ddfb114a6993420e6a071b2a89.png
[20190915000627922.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/3e01390f55fa4820ba7831397e42033f.png
[20190915000659198.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/cfd1ca7ded204e99afac9b4590d5c061.png
[20190915000851482.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/4cc9136440644a5683a958676e98fcda.png
[20190915000926792.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/aea8f8ff647f43d49b29563fe818563e.png
[20190915001245102.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ff374f6fbfc34b9fa4c350041d71e091.png