专栏首页coding个人笔记时间复杂度O(n)和空间复杂度

时间复杂度O(n)和空间复杂度

算法对于敲代码的应该都听过,不管是复杂的还是简单的,衡量算法效率的两个重要指标就是时间复杂度和空间复杂度。

时间复杂度:评估执行程序所需的时间。可以估算出程序对处理器的使用程度。空间复杂度:评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

空间复杂度:对一个算法在运行过程中临时占用存储空间大小的量度。查了很多,对于计算空间复杂度还是没有一个很好的理解,因为有些说需要把算法内部使用的全局变量算在内,有些说只需要把算法内部变量算在内,有些说需要循环几次,每一次的临时变量需要叠加算,有些又说临时变量会被销毁,还是只算一个。所以我们只要记住,空间复杂度就是这个算法运行过程中临时占用的内存。

时间复杂度:你可以简单理解算法运行所需要的时间,我们一般会以牺牲空间复杂度来实现时间复杂度最优。如果单纯以时间来衡量时间复杂度不是很准确,因为相同算法在不同环境或者不同数据下运行时间是不一样的。所以,时间复杂度一般用大O符号表示法。

大O表示法有三个规则:

1.用常数1取代运行时间中的所有加法常数

2.只保留最高阶项

3.去除最高阶的常数

常数阶:

var a = 1;//执行1次
var b = 2;//执行1次
console.log(a  +  b);//执行1次

比如这样的代码,每一句都是执行一次,加起来是三次,套用规则1,这段代码时间复杂度为O(1)。

线性阶:

var a = 1;//执行1次
for(var i = 0; i < n;i++){ 
   console.log(i)//执行n次
}

总共执行了n+1次,套用规则,保留高阶项,去除高阶常数,所以时间复杂度是O(n)。

对数阶:

var a = 1;//执行1次
while (a < n){ 
   a *= 2; //执行了logn次
}

这段代码while里面要判断执行次数,假设执行次数是x那么要成立2^x > n,所以得出来的执行次数就是logn(这是基本的数学了,不懂的话我也无能为力)。应该有人会觉得log的底数是10,而我们这边底数是2,但在算法里面,我们只会用数学的方法把n无限大去比较,所以不管底数是多少,算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。套用规则,这段代码执行次数logn + 1,保留高阶项,去除高阶常数,所以时间复杂度是O(logn)。

平方阶:

for (var i = 0; i < n; i++) { 
// 语句执行n次 
for (var j = 0; j < m; j++) { 语句执行m次
        console.log(i + j); // 语句执行n*m次 
 }}

同样的,这边执行次数是n*m,用数学的方式n和m趋于无穷大的时候,n≈m,于是执行次数就是n^2,所以时间复杂度是O(n^2)。当然还有n的三次方、四次方等。

算法还有很多很多的时间复杂度,你要是数学学得好,你就可以找出更多的时间复杂度,本人要是高中时候还能多找几个,现在只能理解这几个了。

而时间复杂度也是能比较的,单以这几个而言:

O(1)<O(logn)<O(n)<O(n²)<O(n³)

一个算法执行所消耗的时间理论上是不能算出来的,我们可以在程序中测试获得。我们不可能也没必要对每个算法进行测试,我们通过类似上面的方法,就能大概的比较出算法的执行效率。

分享时间复杂度这个概念只是想让大家了解一下我们写的一些代码执行效率是可以比较的,时间复杂度也并不能单纯的以上面单个来看,经常会组合夹杂着出现。

(完)

本文分享自微信公众号 - coding个人笔记(gh_2ce38b49dae1),作者:wade

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-25

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • vue脚手架创建项目

    Vue作为现在前端三大框架之一,又是国人开发的,现在已经越来越火。作为最轻量级的一个前端框架,入门简单,今天用脚手架创建一个最简单的应用。

    wade
  • 哔哩哔哩开源的flvjs

    之前有分享过rtmp和m3u8的直播,后来才有了哔哩哔哩开源的flvjs做,于是就出现了ios不兼容的问题。

    wade
  • 发布npm包

    Npm包管理器不用多讲,用过三大框架的应该都用过。今天讲一下怎么发布自己的npm包。

    wade
  • 02 复杂度分析_pythoner学习数据结构与算法系列

    设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度...

    诡途
  • 数据结构算法入门--一文了解什么是复杂度

    最近会开始更新一个数据结构算法的学习系列,同时不定期更新 leetcode 的刷题。

    材ccc
  • 读张逸的领域驱动设计之应对软件复杂度笔记 原

        Eric Evans认为"很多应用程序最主要的复杂度并不是技术上,而是来自域本身、用户的活动或业务"。最终决定的因素还是因为需求。

    克虏伯
  • 昨天的文章,有朋友给出"更好的"解法,其实并不是...

    昨天推送一道题目分析,一方面学习一个颇具特色的数组,它的取值不大于数组长度;另一方面通过这道题充分体会算法分析、逻辑推理的重要性。只有做好充分的分析,才可能写出...

    double
  • 数据结构和算法

    10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

    分母为零
  • 数据结构与算法 1-4 常见时间复杂度与大小关系

    本系列是我在学习《基于Python的数据结构》时候的笔记。本小节主要介绍一些常见的时间复杂度以及它们之间的大小关系。

    触摸壹缕阳光
  • 数据结构与算法学习笔记之 复杂度分析

    大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜...

    Dawnzhang

扫码关注云+社区

领取腾讯云代金券