复杂度分析

复杂度分析是整个算法学习的精髓,只要掌握它,数据结构和算法的内容基本就掌握了一半。

大O复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,简称时间复杂度。

1、只关注循环执行次数最多的一段代码

只要关注for循环执行次数就可以了,执行n次,所以总时间复杂度就是O(n)。

2、加法法则:总复杂度等于量级最大的那段代码的复杂度

以上代码有三个for循环,sum1循环中循环次数是100,跟n无关,复杂度为O(1),sum2循环中循环次数为n,复杂度为O(n),sum3循环是双重循环,复杂度为O(n²)。最终复杂度就等于量级最大的那段,也就是O(n²)。

3、乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

以上代码有两个方法是,每个方法都有一个for循环,复杂度都为O(n),cal3()方法中调用了f()方法,

根据乘法法则,最终复杂度为O(n²)。

4、常见时间复杂度O(logn)、O(nlogn)

以上代码中,变量i是等比增长的,复杂度就是O(logn)。

空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系,称为空间复杂度。

以上代码,数组a申请了一个大小为n的存储空间,空间复杂度就是O(n)。

最好、最坏情况时间复杂度、平均情况时间复杂度

阅读以上代码,不同情况下,时间复杂度是不一样的。为了表示代码在不同情况下的时间复杂度,我们引入三个概念:最好情况时间复杂度、最坏情况时间复杂度和平均情况时间复杂度。

以上代码中,最好情况时间复杂度是O(1),最坏情况时间复杂度是O(n),平均情况时间复杂度需要引入概率,假设要寻找的元素在数组中与不在数组中各占1/2,数组中n个数据,出现在每个位置的概率为1/n,所以根据概率乘法原则,出现在数组中每个位置的概率为1/2n。那么平均时间复杂度的计算过程为:1*1/2n+2*1/2n+3*1/2n+……+n*1/2n+n*1/2 = (3n+1)/ 4 ,这个就是加权平均值。平均时间复杂度是O(n)。

均摊时间复杂度

以上代码,最好情况复杂度为O(1),数组有空间直接插入数据。最坏情况时间复杂度为O(n),恰巧数组没有空间需要循环遍历一次。平均时间复杂度为O(1),数组长度为n,外加如果越界的一次,概率都是1/(n+1),加权平均的计算过程:1*1/(n+1)+1*1/(n+1)+……+1*1/(n+1)+n*1/(n+1) = O(1)。

我们再来分析这个例子,复杂度为O(1)的情况执行n-1次,才会出现一次O(n),出现的频率是很有规律的。所以针对这样的特殊场景,我们引入均摊时间复杂度,大致思路就是将耗时最多的那一次O(n),均摊到n-1次O(1)上,均摊结果就是O(1)。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,869评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,716评论 3 396
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 166,223评论 0 357
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 59,047评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 68,089评论 6 395
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,839评论 1 308
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,516评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,410评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,920评论 1 319
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,052评论 3 340
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,179评论 1 352
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,868评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,522评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,070评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,186评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,487评论 3 375
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,162评论 2 356

推荐阅读更多精彩内容