算法复杂度O(nlogn)详解

深碍√TFBOYSˉ_ 2022-06-10 07:23 379阅读 0赞

首先看以下程序段：

for（int i=1;i<=n;i++）

\{

for(int j=1;j<=n;j+=i)

\{

..... //复杂度为O(1);

\}

\}

求该程序段的时间复杂度。

可以看出：（1）当i=1时，需要执行n次；

（2）当i=2时，需要执行n/2次；

（3）当i=3时，需要执行n/3次；

.............

（4）当i=n-1时，需要执行n/n-1次；

（5）当i=n时，需要执行n/n次；

每次的时间复杂度为O（1），则总共的时间复杂度为n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)。

1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n是一个调和级数。很早就有数学家研究，比如中世纪后期的数学家Oresme在1360年就证明了这个级数是发散的。Euler(欧拉)在1734年，利用Newton的成果，首先获得了这个调和级数有限多项和的值。

1+1/2+1/3+1/4+...+1/n= ln(n+1)+r(r为常量)

他的证明是这样的：

根据Newton的幂级数有：

ln(1+1/x) = 1/x - 1/2x^2 + 1/3x^3 - ...

于是：

1/x = ln((x+1)/x) + 1/2x^2 - 1/3x^3 + ...

代入x=1,2,...,n，就给出：

1/1 = ln(2) + 1/2 - 1/3 + 1/4 -1/5 + ...

1/2 = ln(3/2) + 1/2\*4 - 1/3\*8 + 1/4\*16 - ...

......

1/n = ln((n+1)/n) + 1/2n^2 - 1/3n^3 + ...

相加，就得到：

1+1/2+1/3+1/4+...1/n = ln(n+1) + 1/2\*(1+1/4+1/9+...+1/n^2) - 1/3\*(1+1/8+1/27+...+1/n^3) + ......

后面那一串和都是收敛的，我们可以定义

1+1/2+1/3+1/4+...1/n = ln(n+1) + r

Euler近似地计算了r的值，约为0.5772156649。这个数字就是后来称作的 [欧拉常数][Link 1]。

回归到程序本身：

则总共的时间复杂度为：

n(1 +1/2+1/3 +1/4 + 1/5+ 1/6+1/7+1/8 +...1/n)

=n(ln(n+1) + r)

=nln(n+1)+rn

因此该程序段的时间复杂度为O（nlogn).

[Link 1]: https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%B8%B8%E6%95%B0

发表评论取消回复

表情：

评论列表（有 0 条评论，379人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】时间复杂度，空间复杂度

文章目录一：时间频度 1.1 度量一个程序(算法)执行时间的两种方法 1.2 基本介绍 1.3 举例说明

骑猪看日落/ 2024年03月02日 10:11/ 0 赞/ 83 阅读

相关算法：算法概述【时间复杂度、空间复杂度】

一、算法定义 > 算法:为了实现业务目的的各种方法和思路就是算法。同样的数据,同样的目的, 不同的算法,不同的方法和思路,效率就会不同 > 算法是一种独立的存在 ,

柔情只为你懂/ 2023年10月05日 12:26/ 0 赞/ 29 阅读

相关算法的时间复杂度和空间复杂度详解

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础

曾经终败给现在/ 2023年06月30日 06:56/ 0 赞/ 112 阅读

相关算法-时间复杂度和空间复杂度

2.9 算法时间复杂度 2.9.1 算法时间复杂度定义在进行算法分析时，语句总的执行次数 T ( n )是关子问题规模n的函数，进而分析 T ( n )随 n

川长思鸟来/ 2022年07月12日 12:46/ 0 赞/ 315 阅读

相关算法复杂度O(nlogn)详解

首先看以下程序段： for（int i=1;i<=n;i++） \{ for(int j=1;j<=n;j+=i) \{ ..... //复杂度为O(1); \}

深碍√TFBOYSˉ_/ 2022年06月10日 07:23/ 0 赞/ 380 阅读

相关经典排序算法（时间复杂度详解）

动画网站 [动画展示排序算法][Link 1] 对比具体实现来看。主要术语解释：稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果

男娘i/ 2022年05月30日 02:43/ 0 赞/ 169 阅读

相关算法的时间复杂度和空间复杂度详解

通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而在证明算法是正确的基础

梦里梦外;/ 2022年04月23日 03:38/ 0 赞/ 231 阅读

相关算法 - 空间复杂度时间复杂度

[关于算法空间复杂度的问题][Link 1] ‘算法空间复杂度’，别以为这个东西多么高大上，我保证你看完这篇文章就能明白。最近在啃算法，发现非常有趣。在我学习的

Bertha 。/ 2022年04月08日 08:29/ 0 赞/ 392 阅读

相关算法复杂度

1. 算法复杂度：大O阶算法： T(n)=O(f(n)) 随着n变大， T(n)增长最慢为最优 ![watermark_t

一时失言乱红尘/ 2022年03月15日 03:00/ 0 赞/ 264 阅读

相关算法复杂度

算法复杂度分为 ‘时间复杂度’ 和 ‘空间复杂度’ 。其作用：时间复杂度是指执行算法所需要的计算工作量；空间复杂度是指执行这个算法所需要的内存空间。（算法的复

小咪咪/ 2021年09月30日 06:40/ 0 赞/ 370 阅读