美文网首页
复杂度分析

复杂度分析

作者: chopin | 来源:发表于2021-05-27 15:40 被阅读0次

什么是复杂度?

算法的复杂度是粗略衡量一个算法执行效率的方法,分为时间复杂度和空间复杂度。

时间复杂度:估算程序指令的执行次数(时间)

空间复杂度:估算所需占用的存储空间

大O表示法

一般用大O表示法来描述复杂度,他表示的是数据规模n对应的复杂度

所有代码的执行时间 T(n) 与每行代码的执行次数 f(n) 成正比。

T(n) = O(f(n))

T(n)表示代码执行的时间;n 表示数据规模的大小;f(n) 表示每行代码执行的次数总和。因为这是一个公式,所以用 f(n) 来表示。公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

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

用大O复杂度表示法,通常我们会忽略常数、系数、低阶

常见的复杂度量级:O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

举个栗子:

假如每一行代码执行时间都是一样的unit_time,这段代码执行时间为(2n+2)*unit_time,所以时间复杂度为O(n)。

多个数据规模的例子:

这个例子里复杂度依赖两个数据规模,所以时间复杂度为O(m+n)

空间复杂度:

表示算法的存储空间与数据规模之间的增长关系。

常见的空间复杂度就是 O(1)、O(n)、O(n2 )

申请了一个大小为 n 的 int 类型数组,同时申请了一个空间存储变量 i,但是它是常量阶的,跟数据规模 n 没有关系,所以我们可以忽略,所以整段代码的空间复杂度就是 O(n)。

算法的优化方向:

1.用尽量少的存储空间

2.用尽量少的执行步骤(执行时间)

根据情况,可以用空间换时间用时间换空间

leetcode斐波那契数列:

https://leetcode-cn.com/problems/fibonacci-number/

相关文章

  • map:169.求众数(投票算法)

    求众数 哈希Map 复杂度分析 时间复杂度:O(N) 空间复杂度: O(N) 投票算法 复杂度分析

  • 复杂度分析

    为什么需要复杂度分析? 大O复杂度表示法 时间复杂度分析 常见复杂度量级 复杂度量级简单说明 空间复杂度 时间复杂...

  • 针对封装数组的简单复杂度分析

    完成了数组的封装之后我们还需对其进行复杂度分析:此处的复杂度分析主要是指时间复杂度分析,算法的时间复杂度反映了程序...

  • 四、复杂度分析& 动态数组的缩容

    复杂度分析 这里分析之前实现的ArrayList和LinkedList的增删改查的复杂度。分析复杂度是要从下面三个...

  • 一个好的算法如何测评

    一个算法的好坏可以根据复杂度分析来测评. 复杂度分析包括时间复杂度和空间复杂度. 1.时间复杂度 需要考虑: 1)...

  • 数据结构与算法 复杂度分析

    复杂度:时间复杂度和空间复杂度。复杂度的分析是学习数据结构与算法的基础! 极简概述 复杂度的分析已经有很多很好...

  • 数据结构与算法学习-复杂度分析

    前言 这一篇笔记主要记录总结了什么是算法复杂度?、为什要做算法复杂度分析?、如何做算法复杂度分析?、常用的复杂度级...

  • 数据结构-复杂度分析

    为什么需要复杂度分析? 复杂度分析实在太重要了。复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构和算法的内容...

  • 算法复杂度分析

    复杂度分析包括: 时间复杂度分析 空间复杂度分析 事后统计法 我们常用事后统计法来统计效率,这种方法也存在一些问题...

  • 模块2作业 朋友圈高性能复杂度

    分析一下微信朋友圈的高性能复杂度 【作业要求】对照模块 2 讲述的复杂度分析方法,分析微信朋友圈的复杂度;针对各个...

网友评论

      本文标题:复杂度分析

      本文链接:https://www.haomeiwen.com/subject/bwpqjltx.html