推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > LifeSmile > 数据结构与算法110—复杂度分析

数据结构与算法110—复杂度分析

LifeSmile 2018-10-18

更多内容访问:www.lifesmile.cn

一、为什么分析复杂度?

    很多人会有疑问,复杂度分为时间和空间复杂度,现在有很多工具监控统计运行时间和占用内存大小,为什么还要去分析呢?

  1. 这种测试的的结果非常依赖当时的测试环境(硬件、网速等)

  2. 结果还受到数据量的影响。

    所以我们需要通过时间空间复杂度来估计执行的效率。

二、时间复杂度分析?

    2.1案例1

  1. int sumNumber(int n){  

  2.     int sum = 0;  

  3.     int i = 1;  

  4.     for (int j = 0; j < n; j++) {  

  5.         sum = sum +j;  

  6.     }  

  7.     return sum;  

  8. }   

  分析:假设执行没一行代码的时间是time,那么上面的代码23行分别执行time,而45行是循环分别执行n*time,7行执行时间是time。那么这段代码执行的时间是:time+time+2*n*time+time=2n*time+3*time

2.2同理看案例2

  1. int calSum(int n){  

  2.     int sum = 0;  

  3.     for (int i = 1; i <n ; i++) {  

  4.         for (int j = 1; j <n ; j++) {  

  5.             sum = sum + i*j;  

  6.         }  

  7.     }  

  8.     return sum;  

  9. }  

  分析:第2,8行执行时间time,3n*time,45行分别是n*n*time

那么这段代码执行时间是:



2.3总结:

  1. 简单的说就是代码执行的时间T(n)与每行执行的次数n,成正比,用数学表达式:T(n)=O(f(n)).所以第一个案例表示为:T(n)=O(2n+3);第二个案例表示为:T(n)=O(2n^2+n+2)

  2. n趋近于无穷大时,低级、系数、常量对增长影响相对很小,所以我们他们的时间复杂程度分别是:T(n)=O(n)T(n)=O(n^2)


2.4集中常见的时间复杂程度:

1.O(1)

    O(1)是常量级时间复杂度,并不是只执行一句代码,案例123行代码虽然是2行执行,但是还是O(1);简单的说只要没有循环递归之类不随n增大而变化得时间复杂度都是O(1).

2.O(n)O(n^2)...O(n^x)

  这类的时间复杂程度已经在案例中分析了,大概就是有循环、多重循环递归这类的。

3.O(logn)O(nlogn)

  1. int i=1;   

  2. while (i <= n) {   

  3.     i = i * 2  

  4. }  


可以看出i每次都会乘以2,什么时候结束循环呢,2^x = n 当等于这个时候就是最好一次循环,现在只需要求出n就知道一共循环了几次,两边同时取2的对数,log2^x = logn--> x= logn(输入公式很麻烦,这默认是2的对数)。前面讲到去掉低阶,系数,常量因此这类时间复杂程度记做为 T(n) = O(logn).

如果理解上面的类容,那么在这基础上再嵌套一个for循环时间复杂程度就是T(n)=O(nlogn).

其他复杂的时间复杂程度可以自己再进行查资料学习。

三、空间复杂程度

时间复杂程度大概表示的是数据规模与算法代码执行时间的正比关系,那么空间复杂程度大概可以理解为数据规模与算法所占空间的正比 关系。知道时间复杂程度,空间复杂程度就非常简单了。

  1. void print(int n) {  

  2.     int i = 0;   

  3.     int[] a = new int[]  

  4.     for (i; i<n; ++i){  

  5.         a[i] = i;  

  6.     }  

  7. }  

和时间复杂程度相似,在上面代码中只有在第3行申请了一个数组,在循环中进行赋值,所以空间复杂程度为O(n),其他的和时间复杂程度相似。

文章是自己在网上学习后简单整理的学习笔记,若有侵权请及时联系删除。




版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《数据结构与算法110—复杂度分析》的版权归原作者「LifeSmile」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注LifeSmile微信公众号

LifeSmile微信公众号:gh_993bd53b4a06

LifeSmile

手机扫描上方二维码即可关注LifeSmile微信公众号

LifeSmile最新文章

精品公众号随机推荐