文档章节

数据结构与算法系列之时间复杂度

AllenOR灵感
 AllenOR灵感
发布于 2017/09/10 01:17
字数 1632
阅读 2
收藏 0

前言

上一篇《数据结构和算法》中我介绍了数据结构的基本概念,也介绍了数据结构一般可以分为逻辑结构和物理结构。逻辑结构分为集合结构、线性结构、树形结构和图形结构。物理结构分为顺序存储结构和链式存储结构。并且也介绍了这些结构的特点。然后,又介绍了算法的概念和算法的5个基本特性,分别是输入、输出、有穷性、确定性和可行性。最后说阐述了一个好的算法需要遵守正确性、可读性、健壮性、时间效率高和存储量低。其实,实现效率和存储量就是时间复杂度和空间复杂度。本篇我们就围绕这两个"复杂度"展开说明。在真正的开发中,时间复杂度尤为重要,空间复杂度我们不做太多说明。

时间复杂度

时间复杂度和空间复杂度是算法效率的度量方法。也就是说,一个好的算法取决于它的时间复杂度和空间复杂度。
函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大。那么,我们说f(n)的增长渐近快于g(n)。

翻译过来就是:如果存在一个临界值,使得f(n)>g(n)永远成立,那么我们就认为"f(n)的增长渐近快于g(n)"。
这里我拿3个函数的增长曲线来说明问题。如下图:
函数一:X = 3n 注释:3乘以n
函数二:Y = 2n^2 注释:n的平方乘以2
函数三:Z = 2n^2 + 3n 注释:n的平方乘以2 + 3乘以n



当n=1时,Y < X < Z.
当n=2时,X < Y < Z.
所以,存在一个值,这个值位于1和2之间,使得X < Y < Z永远成立。我们就称Y的渐进增长快于X,Z的渐进增长快于Y,当然,根据传递性规则,Z的渐进增长也快于X。

定义

算法时间复杂度的定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。
算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

时间复杂度计算方法

1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
最后,得到的最后结果就是时间复杂度。

常见的时间复杂度

按数量级递增排列,常见的时间复杂度有:
常数阶O(1),对数阶O( log n ),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2),立方阶O(n^3),...,k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
也就是:
常用的时间复杂度所耗费的时间从小到大依次是:O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)


时间复杂度顺序表.gif

常数阶

// 常数阶
int n = 0;
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);
printf(“oneSong”);

上面这段代码的时间复杂度是O(1)。因为,按照时间复杂度的定义来说,n和问题的规模没有关系。当然,按照时间复杂度计算方法第一条也可以得出结果为O(1)。

线性阶

// 线性阶int i , 
n = 10086, sum = 0; 
for( i=0; i < n; i++ )
{ 
  sum = sum + i;
}

上面这段代码的时间复杂度是O(n),因为问题规模会随着n的增长而变得越来越大,并且这种增长是线性的。

平方阶

// 平方阶
int i, j, n = 998;
 for( i=0; i < n; i++ )
{ 
    for( j=0; j < n; j++ ) 
    {
       printf(“oneSong”); 
    }
}

上面这段代码外层执行n次,外层循环每执行一次,内层循环就执行n次,那总共程序想要从这两个循环出来,需要执行n*n次,也就是n的平方。所以这段代码的时间复杂度为O(n^2)。

对数阶

// 对数阶
int i = 1, n = 100;
 while( i < n )
{ 
i = i * 2;
}

由于每次i*2之后,就距离n更近一步,假设有x个2相乘后大于或等于n,则会退出循环。于是由2^x = n得到x = log(2)n,所以这个循环的时间复杂度为O(logn)。

算法的空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。
在程序开发中,我们所指的复杂度不做特别说明的情况下,就是指时间复杂度。现在的硬件发展速度之快使得我们完全可以不用考虑算法所占的内存,通常都是用空间换取时间。加之算法的空间复杂度比较难算,所以,无论是在考试中还是在项目开发中,我们都侧重于时间复杂度。所以,空间复杂度,略过。

图片来源参考自:鱼C工作室。感谢鱼C工作室贡献出了这么好的图片。
如非特别说明,笔者所有文章都是原创文章。如果您喜欢这篇文章,转载请注明出处。如果您对数据结构感兴趣,请关注我,后续会更新大量精品文章供大家参考!
PS:本篇文章在博客园也有同步更新,大家也可以通过博客园关注我
http://www.cnblogs.com/wsnb

本文转载自:http://www.jianshu.com/p/688dd3c58a42

共有 人打赏支持
AllenOR灵感
粉丝 10
博文 2634
码字总数 82983
作品 0
程序员
js算法初窥07(算法复杂度)

  算法复杂度是我们来衡量一个算法执行效率的一个度量标准,算法复杂度通常主要有时间复杂度和空间复杂度两种。时间复杂度就是指算法代码在运行最终得到我们想要的结果时所消耗的时间,而空...

zaking
05/30
0
0
趣学算法系列-算法之美

趣学算法系列-算法之美 声明:本系列为趣学算法一书学习总结内容,在此推荐大家看这本算法书籍作为算法入门, 原作者博客链接,本书暂无免费电子版资源,请大家支持正版 书籍简介 本书内容按照...

wwlcsdn000
2017/11/21
0
0
Java版数据结构与算法(一):基础简介

版权声明:本文出自汪磊的博客,未经作者允许禁止转载。 一、前言 项目进入收尾阶段,忙忙碌碌将近一个多月吧,还好,不算太难,就是麻烦点。 数据结构与算法这个系列早就想写了,一是梳理总...

WangLei_ClearHeart
07/18
0
0
算法时间复杂度和空间复杂度的计算

算法,即解决问题的方法。同一个问题,使用不同的算法,虽然得到的结果相同,但是耗费的时间和资源是不同的。 就比如要拧一个螺母,使用扳手还是钳子是有区别的,虽然使用钳子也能拧螺母,但...

tr_ainiyangyang
04/13
0
0
Top K算法详细解析---百度面试

者:码农 问题描述: 这是在网上找到的一道百度的面试题: 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查...

天天顺利
05/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

laravel 微信支付

1.composer加载laravel微信支付第三方文件 composer require "overtrue/laravel-wechat:~4.0" composer require simplesoftwareio/simple-qrcode 1.3.* //composer生成二维码文件 2.改confi......

vio小黑
30分钟前
1
0
学习设计模式——抽象工厂模式

1. 认识抽象工厂模式 1. 定义:提供一个创建一系列相关或互相依赖的对象的接口,而无需指定它们具体的类。 2. 组成结构: AbstractFactory:抽象工厂类,定义创建一系列对象的操作接口 Fact...

江左煤郎
30分钟前
2
0
ES6的let块级作用域和变量不可提升导致一个比较容易出现的错误

今天在写NodeJS代码的时候出现一个变量一直提示未定义,简化后的代码如下: let param = 1;{ console.log(param);} 就在想,不至于啊。不是继承上层的声明吗? 继续看下去,发现原来...

MKjy
36分钟前
2
0
50:nginx访问日记|日记切割|静态文件不记录日记和过期时间

1、nginx访问日记: 日记格式:在主配置文件nginx.conf里搜索log_format; [root@localhost_001 conf]# vim nginx.conflog_format combined_realip '$remote_addr $http_x_forwarded_for ......

芬野de博客
40分钟前
1
0
前后端正常交互的流程

1、评审阶段:产品召集前后端进行需求评审,前后端各自捋清楚自己的业务量以及联调之间工作量,从而进行开发时间评估。 2、开发准备阶段:前后端一起商量需求中需要联调的部分,进行接口的口...

Jack088
40分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部