详解时间、空间复杂度(内含彩蛋~~)

栏目: IT技术 · 发布时间: 4年前

内容简介:学习算法我们首先需要清楚的概念就是时间复杂度和空间复杂度接下来我们就详细讲解一下时间复杂度和空间复杂度,为大家后面的学习打好基础!

目录

  • 一、时间复杂度:执行算法所需要的计算工作量
    • (一)时间复杂度的理解
      • 2.(渐进)时间复杂度定义
    • (二)时间复杂度的计算
  • 二、 空间复杂度:执行这个算法所需要的内存空间

学习算法我们首先需要清楚的概念就是时间复杂度和空间复杂度

接下来我们就详细讲解一下时间复杂度和空间复杂度,为大家后面的学习打好基础!

算法入门书籍挑选点这里~ 帮你快速找到适合自己的算法书籍(详细,内含彩蛋哦~)

一、时间复杂度:执行算法所需要的计算工作量

(一)时间复杂度的理解

1.时间频度定义

我们需先明白:

一个 算法花费的时间 是与 算法中语句的执行次数正比

(也就是说一个算法中语句执行次数越多,花费的时间也就越多)

时间频度:T(n):一个算法中的语句执行次数,记为T(n)

2.(渐进)时间复杂度定义

T(n):算法中基本操作重复执行的次数是问题规模n的某个函数。

f(n):某个辅助函数

算法的(渐进)时间复杂度O(f(n)):

若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f (n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。

记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

O(f(n)) 表示方法称为大O表示法

注意: T(n)不同,但时间复杂度可能相同。

(二)时间复杂度的计算

计算攻略:

  1. 用常数1代替运行时间中的所有 加法常数
(1) T(n)=n 2 +7n+6 ⇒ T(n)=n 2 +7n+1
  1. 修改后的运行次数函数中,只保留最高阶项。
(2)T(n)=n 2 +7n+1 ⇒ T(n)=n 2
  1. 去除最高项系数
(3)T(n)=n 2 ⇒ O(n 2 )

注意:

(1)循环的时间复杂度 = 循环体的复杂度 × 该循环运行次数

(2)单纯的分支结构(不包括在循环结构中)其时间复杂度为O(1)

常见的算法时间复杂度由小到大排序:

常见的算法时间复杂度由小到大依次为:
O(1):常数阶
O(log a n)【O(log 2 n)】:对数阶
O(n):线性阶
O(nlog a n)【O(nlog 2 n)】:线性对数阶
O(n 2 ):平方阶
O(n 3 ):立方阶
O(n k ):k次方阶
O(2 n ):指数阶
随着问题规模n的不断增大,上述时间复杂度越来越大大,算法的执行效率也越来越低

大O表示法推导实例:

1.常数阶 ⇒ O(1)

int n =100;//执行1次
int sum =n*2;//执行1次
System.out println(sum);//执行1次

你可能会问代码一共执行了3次鸭,为什么时间复杂度不是O(3)呢?

这是因为用到了 第一条攻略 :用常数1代替运行时间中的所有 加法常数

本题中:T(n)=3根据第一条攻略:

(1) T(n)=3 ⇒ T(n)=1
(2) T(n)=1 ⇒ O(1)

详解时间、空间复杂度(内含彩蛋~~)

2.线性阶 ⇒ O(n)

int i= 0,sum=0;
for(i=0;i<n;i++){//for循环执行n次
sum=2*i;//执行一次for循环此语句执行一次
System.out.println(sum);//执行一次for循环此语句执行一次
}

所以:T(n)=2n

第三条攻略:去除最高项系数

本例中根据 第三条攻略可得

(1) T(n)=2n ⇒ T(n)=n
(2) T(n)=n ⇒ O(n)

详解时间、空间复杂度(内含彩蛋~~)

3.平方阶 ⇒ O(n 2 )

例1:

int i,j=0;
for(i=0;i<n;i++){//执行n次
	for(j=0;j<n;j++){//执行n次
		System.out.println(i + " " + j );
	}
}

所以:T(n)=n 2

T(n)=n 2 ⇒ O(n 2 )

详解时间、空间复杂度(内含彩蛋~~)

例2:

int i,j=0;
for(i=0;i<n;i++){//执行n次
	for(j=i;j<n;j++){//注意j=i
		System.out.println(i + " " + j );
	}
}

当i=0,第二个for循环执行n次

当i=1,第二个for循环执行n-1次

当i=2,第二个for循环执行n-2次

当i=n-1,第二个for循环执行1次

执行总数T(n)=n+(n-1)+(n-2)+……1= 详解时间、空间复杂度(内含彩蛋~~) + 详解时间、空间复杂度(内含彩蛋~~) = (n 2 +n)

根据第二条攻略、第三条攻略可得:

第二条攻略:修改后的运行次数函数中,只保留最高阶项。

第三条攻略:去除最高项系数
T(n)= (n 2 +n) ⇒ T(n)= n 2
T(n)= n 2 ⇒ O(n 2 )

详解时间、空间复杂度(内含彩蛋~~)

二、 空间复杂度:执行这个算法所需要的内存空间

空间复杂度:

对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

n为问题的规模,f(n)为算法所占存储空间的函数。

空间复杂度分类:

O(1)情况:

当算法的存储空间大小固定,与输入规模没有直接的关系时,空间复杂度记作O(1)。

O(n)情况:

当算法分配的空间和输入规模n成正比时,空间复杂度记作O(n)。

三、彩蛋

我将入门算法书中时间复杂度、空间复杂度讲解部分为大家截出来了,有需要的宝宝可以自取。

链接: https://pan.baidu.com/s/1mrMeuLv11Bf09zrE-DhFLA

提取码:yw8d

欢迎大家来公号“小乔的编程内容分享站”来找小乔玩~

一起学习 Java 基础+算法~

还有更多资源等你来拿哦~


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Getting Real

Getting Real

Jason Fried、Heinemeier David Hansson、Matthew Linderman / 37signals / 2009-11-18 / USD 24.99

Getting Real details the business, design, programming, and marketing principles of 37signals. The book is packed with keep-it-simple insights, contrarian points of view, and unconventional approaches......一起来看看 《Getting Real》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具