理解算法的复杂度

关于时间复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度可被成为是渐近的(asymptotic analysis),渐近是指在数学分析中是一种描述函数在极限附近的行为的方法,有多个科学领域应用此方法。

(1)在计算机科学中,算法分析考虑给定算法在输入非常大的数据集时候的性能。

(2)当实体系统的规模变得非常大的时候,分析它的行为。

举个简单的例子:函数f(n)=3n^2+3n ,当n变得非常大的时候,函数的第二项3n要远比第一项n^2影响小,所以我们对于这个函数的复杂度描述可以近似认为是O( n^2 ),注意到大O符号里隐藏着一个常数C,所以f(n)里一般不加系数,简单的来说,我们在评估时间复杂度影响的时候,为了简化表示,只看对其影响最大的主要路径,其他的细枝末叶都可以忽略。

算法时间复杂度分析是一个很重要的问题,任何一个程序员都应该熟练掌握其概念和基本方法,而且要善于从数学层面上探寻其本质,才能准确理解其内涵。

常见的算法时间复杂度由大到小如下:

常见的算法时间复杂度由小到大依次为:

Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n^2)<Ο( n^3 )<Ο(2^n)<Ο(n!) 随着问题规模 n的不断增大,时间复杂度不断增大,算法的执行效率越低。

序号

名称

运行时间

举例

1

常数阶

O(1)

数组按下标访问

2

对数阶

O(log2 n)

二分搜索

3

线性阶

Ο(n)

无序数组的搜索

4

线性对数阶

Ο(nlog2n)

快速排序算法

5

平方阶

Ο(n^2)

冒泡排序和插入排序算法

6

立方阶

Ο(n^3)

矩阵乘法的基本实现

7

指数阶

Ο(2^n)或O( k^n )

使用动态规划解决旅行推销员问题

8

阶乘阶

O(n!)

通过暴力搜索解决旅行推销员问题

看下面一个图,从直观上感受一下他们的曲线走势:

根据经验值,在上面表格中只有前4个的时间复杂度是比较快的,一般可以在秒级别返回比如一些排序算法,但稍微大一些的n就会令这些算法不能动了,当n=10万的时候,平方阶一般需要几分钟才能计算完毕,而立方阶则需要200多天,至于更后面的复杂度得需要几年才能运算完毕。如果大于10万,则更加糟糕,所以在设计程序的时候我们得注意相关算法的时间复杂度。

关于空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了,因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说,一般都比较简短,算法本身所占用的存储空间较少,但运行时需要一个附加堆栈,从而占用较多的临时工作单元;若写成非递归算法,一般可能比较长,算法本身占用的存储空间较多,但运行时将可能需要较少的存储单元。

对于一个算法,其 时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。

总结

本文主要介绍了算法的时间复杂度和空间复杂度的概念和定义,一个好的算法往往能大幅度提升程序的性能,一个坏的算法往往会拖慢整个程序的运行,因此了解算法的复杂度对我们日常开发和写代码则很有指导意义,在掌握本篇文章的知识之后,我们就可以学以致用,对于一些常见的数据结构试着去分析一下其复杂度,比如数组,链表,Hash表,二叉树等。

原文发布于微信公众号 - 我是攻城师(woshigcs)

原文发表时间:2018-09-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏深度学习那些事儿

pytorch新手需要注意的隐晦操作Tensor,max,gather

先看官方的介绍: 如果input是一个n维的tensor,size为 (x0,x1…,xi−1,xi,xi+1,…,xn−1),dim为i,然后index必须...

1.4K8
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

假设给定一个由字母和小数点组成的字符串,把字符串按块翻转,其中连续的小数点为一块,连续的字母为一块。例如 'ab..bc...cd.' 翻转后为 '.cd......

2274
来自专栏程序员叨叨叨

6.6 条件操作符(Conditional Operators)

expr1的计算结果为true或者flase,如果是true,则expr2执行运算,否则expr3 被计算。

1193
来自专栏IT可乐

Java数据结构和算法(一)——简介

  本系列博客我们将学习数据结构和算法,为什么要学习数据结构和算法,这里我举个简单的例子。   编程好比是一辆汽车,而数据结构和算法是汽车内部的变速箱。一个开车...

3119
来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第五章)

读书会是一种在于拓展视野、宏观思维、知识交流、提升生活的活动。PPV课R语言读书会以“学习、分享、进步”为宗旨,通过成员协作完成R语言专业书籍的精读和分享,达到...

5029
来自专栏落影的专栏

程序员进阶之算法练习(四)

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

45710
来自专栏磐创AI技术团队的专栏

快速学习 Python 的全套 14 张思维导图(附高清版下载)

基础知识图一包括了基本规则、Python语言特点、计算机语言、如何运行Python、变量赋值五个方面,辅助你快速掌握Python编程的基底知识。

2513
来自专栏机器人网

机器学习中基本的数学符号是什么?

本文介绍了机器学习中的基本数学符号。具体来说有算数符号,包括各种乘法、指数、平方根以及对数;数列和集合符号,包括索引、累加以及集合关系。此外,本文还给出了 5 ...

7796
来自专栏Python小屋

Python使用scipy进行多项式计算与符号计算

在扩展库numpy和scipy中都有poly1d,用法一样,实际上是同一个库,scipy是基于numpy的。有图为证 ? 本文代码主要演示如何使用poly1d进...

4926
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

3776

扫码关注云+社区

领取腾讯云代金券