精华内容
下载资源
问答
  • 计算机科学时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项...

    概念

    时间复杂度

    计算机科学中,时间复杂性,又称时间复杂度算法时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况,时间复杂度表示的是一个算法的时间增长趋势,因为一个算法在不同机器上部署的时候,每个机器的性能大不相同,所以运算时间也不同,评估一个算法在运算时间上的性能,我们通常用时间复杂度来评估一个算法的时间运算概念。

    空间复杂度

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

    常见算法的时间复杂度举例(此处用JAVA语言分析举例)

    常见的时间复杂度

    名称 大O表示法
    常数阶 O(1)
    对数阶 O(log_{2}N
    线性阶 O(N)
    线性对数阶 O(Nlog_{2}N
    平方阶 O(N^2)
    立方阶 O(N^3)
    k次方阶 O(N^k)
    指数阶 O(2^{N})

    常见的算法时间复杂度由小到大依次为:O(1)<O(log_{2}N)<O(N)<O(Nlog_{2}N)<O(N^2)<O(N^3)<O(N^k)<O(2^{N})

    常数阶表达式代码:

    int i=2;
    int j=3;
    int sum=i+j;

    对数阶表达式代码:

    int i=1;
    while(i<n){
      i=i*2;
    }

    在while循环里面,每次都将乘以2,乘完之后,i的距离就越来越近了。假设循环x次之后,i就大于2了,此时这个循环就推出了,也就是2的x次方=n;

    线性阶表达式代码:

     int j=0;
    for(int i=1;i<=N;i++){
        
            j++;
    }

    在for循环里面的代码会循环n遍

    线性对数阶表达式代码:

     int j=0;
    for(int i=1;i<=N;i++){
        
            j=1;
       while(j<N){
        j=j*2;
    }
    }

    for循环里面嵌套了一个while循环 for循环的时间复杂度为O(N),while循环的时间复杂度为O(log_{2}N)所以此代码的时间复杂度为O(Nlog_{2}N

    平方阶表达式代码:

    int m=0;
    for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
       m++;
    }
    }

    上述代码为两个for循环代码的嵌套一个for循环的时间复杂度为O(N),则嵌套for循环代码的时间复杂度为O(N^{2}),依次类推O(N^{k})为k个for循环嵌套

    尽量避免指数阶算法

    空间复杂度代码表示

    名称 大O表示法
    常数阶 O(1)
    线性阶 O(N)
    平方阶 O(N^{2})

    常数阶表达式代码:

    int i=0;
    int j=0;
    

    线性阶表达式代码:

    int [] num=new int[N];
    for(int i=0;i<N;i++){
     num[i]=i;
    }

    在内存中创建一个长度为N的一维数组,它的空间复杂度就为O(N);

    平方阶表达式代码:

    int [][] num=new int[N][N];
    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        num[i][j]=i+j;
    }
    }

    在内存中创建一个长度为N行N列的二维数组,它的空间复杂度就为O(N^{2})。

    通常一个算法的复杂度是由其输入量决定的,随着输入的增加,不同算法的复杂度增长速度不同,为了降低算法复杂度,应当同时考虑到输入量,设计较好的算法。

    展开全文
  • 实例:反转一个单链表 思路:按原始顺序迭代结点,并将它们逐个移动到列表的头部 注意:黑色结点 23 是原始的头结点。 1.我们将黑色结点的下一个结点 ...该算法,每个结点只移动一次。 因此,时间复杂度为 O...

    实例:反转一个单链表
    思路:按原始顺序迭代结点,并将它们逐个移动到列表的头部
    注意:黑色结点 23 是原始的头结点。
    1.我们将黑色结点的下一个结点 6移动到列表的头部:
    这里写图片描述
    2. 然后,我们将黑色结点的下一个结点15移动到列表的头部:
    这里写图片描述
    3. 黑色结点的下一个结点现在是空。因此,我们停止这一过程并返回新的头结点 15。
    这里写图片描述
    在该算法中,每个结点只移动一次。
    因此,时间复杂度为 O(N),其中 N 是链表的长度。我们只使用常量级的额外空间,所以空间复杂度为 O(1)。

    展开全文
  • 快速理解时间复杂度与空间复杂度

    千次阅读 多人点赞 2018-05-11 17:48:05
    我们程序通常采用以空间时间的方式来提高项目运行效率。 先给大家说一个最常见的简单的,时间复杂度是以n为变量,程序的运行次数随n的变化而变化。for(int i=0;i&lt;n;i++){ }当只有一层for循环的时候...

    1.首先,时间复杂度与空间复杂度是对立的,时间复杂度越低,空间复杂度就越高。我们在程序中通常采用以空间换时间的方式来提高项目运行效率。

    先给大家说一个最常见的简单的,时间复杂度是以n为变量,程序的运行次数随n的变化而变化。

    for(int i=0;i<n;i++){
    
    }

    当只有一层for循环的时候时间复杂度就是O(n)如果两层for循环如下所示:

    for(int i=0;i<n;i++){
    
    for(int j=0;i<n;i++){
    
    }
    }

    那么它时间间复杂度就是O(n^2),同理三层for循环就是O(n^3)

    2. 常数时间复杂度

    int i=0;
    i=(i+n)*n;
    system.out.println("我只执行一次"+i);
    
    
    

    当我们的语句是一句一句向下执行时,执行多少语句,时间复杂度都是O(1)


    3.对数阶
    接着看如下代码:

    int number=1;
    while(number<n){
    number=number*2;
    //时间复杂度为O(1)的算法
    ...
    }
    • 可以看出上面的代码,随着number每次乘以2后,都会越来越接近n,当number不小于n时就会退出循环。假设循环的次数为X,则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。

    java中各种排序算法的时间复杂度。





    展开全文
  • 我们程序通常采用以空间时间的方式来提高项目运行效率。 一、时间复杂度 先给大家说一个最常见的简单的,时间复杂度是以n为变量,程序的运行次数随n的变化而变化。for(int i=0;i<n;i++){ }当只有一层...

    首先,时间复杂度与空间复杂度是对立的,时间复杂度越低,空间复杂度就越高。我们在程序中通常采用以空间换时间的方式来提高项目运行效率。

    一、时间复杂度

    先给大家说一个最常见的简单的,时间复杂度是以n为变量,程序的运行次数随n的变化而变化。

    for(int i=0;i<n;i++){
    }
    

    当只有一层for循环的时候时间复杂度就是O(n)如果两层for循环如下所示:

    for(int i=0;i<n;i++)
    {
    for(int j=0;i<n;i++){
    }
    }

    那么它时间间复杂度就是O(n^2),同理三层for循环就是O(n^3)

    2. 常数时间复杂度

    int i=0;
    i=(i+n)*n;
    system.out.println("我只执行一次"+i);
    

    当我们的语句是一句一句向下执行时,执行多少语句,时间复杂度都是O(1)


    3.对数阶
    接着看如下代码:

    int number=1;
    while(number<n){
    number=number*2;
    //时间复杂度为O(1)的算法

    }
    • 可以看出上面的代码,随着number每次乘以2后,都会越来越接近n,当number不小于n时就会退出循环。假设循环的次数为X,则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。

    二、空间复杂度

      一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度,可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外,还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。  
    (1)固定部分。这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间(即代码空间)、数据空间(常量、简单变量)等所占的空间。这部分属于静态空间。
    (2)可变空间,这部分空间的主要包括动态分配的空间,以及递归栈所需的空间等。这部分的空间大小与算法有关。
    一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))  其中n为问题的规模,S(n)表示空间复杂度。

    【考考你】

    好了,我想到这里,两个复杂度的意思你是否已经弄明白了吧,明白的点个赞,没明白的留个言。

    明白的,不妨试试看看那下面这段代码的时间复杂度T(n)、空间复杂度S(n)分别是多少?回答后连续下滑查看答案。

    for(int i=0; i<n; i++) {
        int[] arr1 = new int [5];
        for (int j = 0; j < n/2; j++) {
            int[] arr2 = new int [n];
        }
    }





















    解:

    从这里看出:T(n) = (1/2) n^2,S(n) = (1/2) n^3 + 5n

    随着n趋于无穷大的时候,最影响他们的是(1/2) n^2和(1/2) n^3,我们省略其常数系数即可得到复杂度关系,即这段代码的时间复杂度为T(n) = O( n^2),空间复杂度为S(n) = O(n^3)

    注:空间复杂度即占用空间大小,这里变量占用空间为5n+(1/2) n^3,即变量个数。

    展开全文
  • Abstract:算法分析包括事后统计和事前分析估算...而算法的空间复杂度则是对算法运行过程临时占用存储空间大小的量度。 算法分析证明算法正确性分析算法时间复杂度:反映算法优劣,通过依据该算法编制的程序计...
  • 一、时间复杂度 「 大O符号表示法 」,即 T(n) = O(f(n)) 我们先来看个例子: ... 大O符号表示法时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个...
  • 理解什么是时间复杂度和空间复杂度 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但过程消耗的资源和时间却会有很大的区...
  • 对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽然结果相同,但过程消耗的资源和时间却会有很大的区别,比如快速排序与猴子排序:)。...
  • 有关时间复杂度,空间复杂度通俗的理解 今天,复习C语言知识时,碰到了一个非常有趣的题目,题目如下: 一个数组除了两个数字之外,其余数字均出现了两次,如{1, 2, 3, 4, 5, 3, 2, 1}。查找出这两...
  • 1、时间复杂度:一个程序(算法实现)计算机上从开始运行到结束耗费的时间,且随着输入数据量的不断增大(无限大),耗费时间的量级也不一样,通过时间复杂度来判定一个程序实现消耗时间的量级程度,从而判断该...
  • 时间复杂度及空间复杂度直白理解/快排/冒泡 常常算法类的文章里看到时间复杂度,空间复杂度的名词,但是对其中的意思不是很清楚,但是大概是知道,复杂度代表了一个算法的运行效率,复杂度越大说明这个算法运行效率越...
  • 对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但过程消耗的资源和时间却会有很大的区别。 衡量不同算法算法的优劣,主要要从算法所占用的「时间」和「空间」两个维度和考量。 时间维度:是指...
  • 空间复杂度:对一个算法运行过程临时占用存储空间大小的量度,记做S(n)=O(f(n)) 总结:时间复杂度指的是语句执行次数,空间复杂度指的是算法所占的存储空间 二、时间复杂度 1.计算方法 用常数1代替运行时间...
  • 百度百科解释: 计算机科学时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数...
  • 理论上来说,a是fun()函数的局部变量,而局部变量的内存空间应该该函数运行结束后即释放掉,也就是说a变量的空间应该fun()函数运行结束后即释放掉,所以主函数用用p来接收a的首地址是没有意义的,因为p将指向...
  • 换个角度—同一个东西在时间上千变万化,频率上不过尔尔 乐谱 在时间上跳跃(想起了周董的【窗外的麻雀,电线杆...苹果不动,是牛顿的世界往上走了—牛顿在时间的进程往上了,然而空间变了(狗头.jpg) ...
  • Oracle表空间理解

    千次阅读 2010-07-09 11:57:00
    概述 Oracle数据库经过长时间的发展,很多用户都很了解Oracle用户表空间了,这里我发表一下个人理解,和大家讨论讨论。SQL Server数据库与Oracle数据库之间最大的区别要属表空间设计。Oracle数据库开创性地...
  • VMWare增加Linux文件系统空间Linux虚拟机使用过程,随着时间的推移,有时候分配的空间不足,那么就需要增加空间,但是虚拟机默认是可以缩减空间,而没有增加空间,那么需要手动进行增加,该文档就是教你...
  • 尤其是各类主要考验算法设计的OJ,输入是固定的,程序大小主要也依赖于编译/语言等底层实现,能由高级的,可以被抽象为函数的算法优化的只有实现算法过程使用的额外辅助空间的大小了,比如排序算法,有些可以...
  • 时间空间复杂度

    2020-03-24 20:34:52
    理解时间空间复杂度 接触时间复杂度,空间复杂度的概念以来,只是大概知道是用来判断代码占用时间和空间多少。时间,空间复杂度越低,代码越好。本篇文章用来明确时间空间复杂度的概念。 书上时间复杂度的概念...
  • 这篇博文讲解的是本人多多维数组和多维空间理解。这里使用到了新的理解的方式,...一维空间表示线段,二维表示面,三维表示立体空间,四维表示某个时间的立体空间。后者包含前者。具体为:线组成面,面组成立
  • 通过马尔可夫模型统计出人体在空间中的位置状态转移概率矩阵及其状态持续时间矩阵,生成日常行为模板。根据当前行为与日常行为模板的相似度可检测出反常习惯和突发异常行为,同时可根据不同区域的行为模式分析人的意图...
  • 1 光谱分辨率、空间分辨率、时间分辨率 2 全色图像、多光谱图像、高光谱图像 2.1 全色图像 2.2 多光谱图像 2.3 高光谱图像 参考资料 1 光谱分辨率、空间分辨率、时间分辨率 遥感(Remote Sensing),可以理解为...
  • 空间复杂度计算的方法和时间复杂度相似的。时间复杂度是关注于问题规模n。...例如:算法有定义了数组flag[n] [n],它的空间复杂度就是O(n^2)。 3、递归型算法(和2很类似) 空间复杂度=递归调用的深度
  • 对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽然结果相同,但过程消耗的资源和时间却会有很大的区别,比如快速排序与猴子排序:)。...
  • 算法时间复杂度理解

    2018-09-27 10:10:28
    描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 这里进行归纳一下它们代表的含义: 这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。 O后面的...
  • 1、百度词条给的解释:空间复杂度(Space Complexity)是对一个算法运行过程临时占用存储空间大小的量度,记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n...
  • 文章首发于浩瀚先森博客 堆栈的概念脑海里已经存在有一段时间了,今天就测试来整理下Heap堆。栈以后再说。 堆区不像全局变量和局部变量总是有指定的内存大小,它是为了程序运行时动态分配内存而设定的一块区域。...
  • python字典的理解

    2021-01-09 20:27:43
    dict可以用需要高速查找的很多地方,Python代码几乎无处不在,正确使用dict非常重要,需要牢记的第一条就是dict的key必须是不可变对象。 这是因为dict根据key来计算value的存储位置,如果每次计算相同的key...
  • 1、概述 研究并发程序时,我们需要了解java关键字volatile和synchronized关键字的使用以及lock类的用法。...(2)对该变量操作完成后,某个时间再把变量刷新回主内存。 那么我们再了解下锁提供的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,352
精华内容 940
关键字:

在空间中理解时间