Java数据结构之复杂度篇

目录
  • 一.算法效率
  • 二. 时间复杂度
    • 1.时间复杂度的概念
    • 2.大O的渐进表示方法
    • 3.实例分析与计算
  • 三.空间复杂度
    • 1.空间复杂度的概念
    • 2.实例分析与计算
  • 四.写在最后

一.算法效率

算法效率分析分为两种：时间效率、空间效率。其中时间效率被称为时间复杂度，空间效率被称为空间复杂度。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额 外空间

由于早期计算机储存容量很少，所以通常是浪费时间来换取空间。而随着计算机的高速发展，计算机的存储容量已经达到了很高水平，所以现在通常是浪费空间换取时间

二. 时间复杂度

1.时间复杂度的概念

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。但是一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。全部算法的上机测试显然是不现实的。于是才有了时间复杂度的分析方式：算法中的基本操作的执行次数，是为算法的时间复杂度。

有些算法的时间复杂度存在最坏、最好和平均情况。一般来说，实际情况中，我们所求的时间复杂度指的是最坏情况

最坏情况：任意输入规模的最大运行次数(上界) 平均情况：任意输入规模的期望运行次数 最好情况：任意输入规模的最小运行次数(下界)

2.大O的渐进表示方法

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用的就是大O的渐进表示法

接下来我们看看推导大O阶的基本原则

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

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

3.实例分析与计算

//计算bubbleSort的时间复杂度
void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }

该算法最坏情况下执行了(N*(N-1))/2次，通过推导大O阶方法可以得出其时间复杂度为O(N)

// 计算binarySearch的时间复杂度
    int binarySearch(int[] array, int value) {
        int begin = 0;
        int end = array.length - 1;
        while (begin <= end) {
            int mid = begin + ((end-begin) / 2);
            if (array[mid] < value)
                begin = mid + 1;
            else if (array[mid] > value)
                end = mid - 1;
            else
                return mid;
        }
        return -1;
    }

该算法最坏情况下执行O(logN)次，时间复杂度为 O(logN)。ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。该算法为二分查找，可以通过画图来借助理解，得出表达式为：N/2^X=1，X就是执行操作的次数

// 计算阶乘递归factorial的时间复杂度？
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1) * N;
    }

基本操作递归了N次，时间复杂度为O(N)

// 计算斐波那契递归fibonacci的时间复杂度
    int fibonacci(int N) {
        return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
    }

基本操作递归了2^N次，时间复杂度为O(2^N)

三.空间复杂度

1.空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，而是算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法

2.实例分析与计算

// 计算bubbleSort的空间复杂度
    void bubbleSort(int[] array) {
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if (array[i - 1] > array[i]) {
                    Swap(array, i - 1, i);
                    sorted = false;
                }
            }
            if (sorted == true) {
                break;
            }
        }
    }

该算法使用了常数个额外空间，所以空间复杂度为 O(1)

// 计算fibonacci的空间复杂度
    int[] fibonacci(int n) {
        long[] fibArray = new long[n + 1];
        fibArray[0] = 0;
        fibArray[1] = 1;
        for (int i = 2; i <= n ; i++) {
            fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
        }
        return fibArray;
    }

该算法动态开辟了N个空间，空间复杂度为 O(N)

// 计算阶乘递归Factorial的时间复杂度
    long factorial(int N) {
        return N < 2 ? N : factorial(N-1)*N;
    }

该算法递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

四.写在最后

由于期末专业课较多，加上自己自控力不足，导致断更了一段时间。寒假决定洗心革面，把断更的博文都补起来。博主在写博客过程中可能出现一些错误，望大家斧正，以及由任何问题可以在评论区或者私信与博主交流。希望大家寒假能有所收获，一起卷起来！

到此这篇关于Java数据结构之复杂度篇的文章就介绍到这了,更多相关Java 复杂度内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java均摊复杂度和防止复杂度的震荡原理分析

    本文实例讲述了Java均摊复杂度和防止复杂度的震荡.分享给大家供大家参考,具体如下: 关于上一节封装数组的简单复杂度分析方法中我们对添加操作的时间复杂度归结为O(n)是考虑了扩容操作(resize)在内的.就addLast(e)操作而言,时间复杂度为O(1),在考虑最坏情况下,每次添加均会触发扩容操作,需要移动n个元素,因此此时addLast操作的时间复杂度为O(n). (1)addLast(e)均摊时间复杂度分析 resize(n)   O(n) 假设当前capacity=8,并且每一次添加操

  • Java 关于时间复杂度和空间复杂度的深度刨析

    Java 关于时间复杂度和空间复杂度的深度刨析

    目录 1.算法效率 2.时间复杂度 2.1时间复杂度的概念 2.2大O的渐进表示法 2.3常见时间复杂度计算 2.3.1常用的时间复杂度量级 2.3.2常见示例举例 2.3.2示例答案及分析 3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间 如今我们更关注的是时间复杂度,而对空间复杂度已不再关注. 2.时间复杂度 2

  • Java算法之时间复杂度和空间复杂度的概念和计算

    Java算法之时间复杂度和空间复杂度的概念和计算

    一.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间. 在计算机发展的早期,计算机的存储容量很小.所以对空间复杂度很是在乎.但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度.所以我们如今已经不需要再特别关注一个算法的空间复杂度.因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法 二.时间复杂度 2.1

  • Java时间复杂度、空间复杂度的深入详解

    Java时间复杂度、空间复杂度的深入详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 总结 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么

  • Java 数据结构之时间复杂度与空间复杂度详解

    Java 数据结构之时间复杂度与空间复杂度详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么是时间

  • 从零开始学Java之关系运算符

    目录 引言 定义 实例 注意点 举例 总结 引言 ♀ 小AD:明哥,我怎么就那么讨厌刺客,凭什么我就打不过他们,每次把我秒了. ♂ 明世隐:这是因为英雄克制,刺客就是用来对方脆皮的. ♀ 小AD:所以这个叫克制关系? ♂ 明世隐:对,但是刺客却害怕战士型英雄. ♀ 小AD:战士相对被肉克制?肉被射手克制? ♂ 明世隐:差球不多!是一种克制关系,当然不是绝对的,如果段位相差过多,就当我没说.那你跟我什么关系? ♀ 小AD:师徒?大腿? ♂ 明世隐:总之无形之中是不是有一种关系的存在 ? ♀ 小AD

  • java实现堆排序以及时间复杂度的分析

    java实现堆排序以及时间复杂度的分析

    完全二叉树:从上到下,从左到右,每层的节点都是满的,最下边一层所有的节点都是连续集中在最左边. 二叉树的特点就是左子节点是父节点索引值的2倍加一,右子节点是父节点索引值的2倍加二 堆分为两种:大顶堆和小顶堆         大顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值         小顶堆:在完全二叉树基础上,每个节点的值都大于或等于其左右子节点的值 堆排序就是根据先构建好的大顶堆或小顶堆进行排序的. 怎么构建大顶堆:         假如一个数组是:int[] arr

  • Java数据结构之复杂度篇

    目录 一.算法效率 二. 时间复杂度 1.时间复杂度的概念 2.大O的渐进表示方法 3.实例分析与计算 三.空间复杂度 1.空间复杂度的概念 2.实例分析与计算 四.写在最后 一.算法效率 算法效率分析分为两种:时间效率.空间效率.其中时间效率被称为时间复杂度,空间效率被称为空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间 由于早期计算机储存容量很少,所以通常是浪费时间来换取空间.而随着计算机的高速发展,计算机的存储容量已经达到了很高水平,所

  • Java数据结构之顺序表篇

    Java数据结构之顺序表篇

    目录 一.线性表 二.顺序表 1.概念及结构 2.顺序表的实现 打印顺序表 获取顺序表的有效长度 在pos位置新增元素 判断是否包含某个元素 查找某个元素对应的位置 获取/查找pos位置的元素 给pos位置的元素设为value 删除第一次出现的关键字key 清空顺序表 3.顺序表的优.缺点 三.顺序表的实现代码汇总 一.线性表 线性表( linear list ) 是 n 个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见 的线性表:顺序表.链表.栈.队列.字符串

  • Java数据结构之Map与Set专篇讲解

    Java数据结构之Map与Set专篇讲解

    目录 ①只出现一次的数字 ②宝石与石头 ③坏键盘打字 ④复制带随机指针的链表 ①只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 输入: [2,2,1]输出: 1 首相我们可能会想到用位运算直接解决,但我们也可以用hash色条解决. public int singleNumber(int[] nums) { int single = 0; for (int num : nums) { single ^= num; } ret

  • Java数据结构之图(动力节点Java学院整理)

    Java数据结构之图(动力节点Java学院整理)

    1,摘要: 本文章主要讲解学习如何使用JAVA语言以邻接表的方式实现了数据结构---图(Graph).从数据的表示方法来说,有二种表示图的方式:一种是邻接矩阵,其实是一个二维数组:一种是邻接表,其实是一个顶点表,每个顶点又拥有一个边列表.下图是图的邻接表表示. 从图中可以看出,图的实现需要能够表示顶点表,能够表示边表.邻接表指是的哪部分呢?每个顶点都有一个邻接表,一个指定顶点的邻接表中,起始顶点表示边的起点,其他顶点表示边的终点.这样,就可以用邻接表来实现边的表示了.如顶点V0的邻接表如下: 与

  • Java数据结构与算法入门实例详解

    Java数据结构与算法入门实例详解

    第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的

  • Java数据结构学习之树

    Java数据结构学习之树

    一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的

  • Java数据结构之哈夫曼树概述及实现

    Java数据结构之哈夫曼树概述及实现

    一.与哈夫曼树相关的概念 概念 含义 1. 路径 从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度 路径上的分支数目 3. 树的路径长度 长度从根到每个结点的路径长度之和 4. 带权路径长度 结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度 树中所有叶子结点的带权路径长度之和 二.什么是哈夫曼树 定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.

  • Java数据结构之链表详解

    Java数据结构之链表详解

    一.链表的介绍 什么是链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,操作复杂.由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的

  • java数据结构-堆实现优先队列

    java数据结构-堆实现优先队列

    目录 一.二叉树的顺序存储 1.堆的存储方式 2.下标关系 二.堆(heap) 1.概念 2.大/小 根堆 2.1小根堆 2.2大根堆 3.建堆操作 3.1向下调整 4.入队操作 4.1向上调整 4.2push 入队的完整代码展示 5.出队操作 5.1pop 出队代码完全展示 6.查看堆顶元素 7.TOK 问题 7.1TOPK 8.堆排序 文章内容介绍大纲 一.二叉树的顺序存储 1.堆的存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完

  • Java数据结构与算法之循环队列的实现

    Java数据结构与算法之循环队列的实现

    目录 概述 循环队列 循环队列实现 改变队列大小 enqueue 方法 dequeue 方法 main 完整代码  概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 循环队列 循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题. 循环队列的底层依然是数组, 不过增加了指向头和尾的指针. 循环队列实现 判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear,

随机推荐