本站消息

站长简介


前每日优鲜python全栈开发工程师,自媒体达人,逗比程序猿,钱少话少特宅,我的公众号:想吃麻辣香锅

  java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-03(260)

2021-04(132)

2021-05(89)

2021-06(38)

初识算法-空间复杂度

发布于2021-06-08 12:42     阅读(616)     评论(0)     点赞(9)     收藏(0)


0

1

2

3

4

计算机的软硬件都经历了一个比较漫长的历史,作为为运行提供环境的内存,从512k 、1M、2M、4M…8G、16G、32G,因此,早期算法在运行过程中对内存占用情况也是一个经常要考虑的问题,我们用算法的空间复杂度来描述算法对内存的占用情况

java中常见的内存占用
在这里插入图片描述
计算机访问内存的方式都是一次一个字节
在这里插入图片描述
一个引用(机器地址)需要8个字节表示
例如:Data date = new Date(),则这个data需要8个字节表示
创建一个对象,比如new Date(),除了Date对象内部存储的数据(例如年月日)占用内存,该对象本身也有内存开销,每个对象的自身开销是16个字节,用来保存对象的头信息。
一般内存的使用,如果不够8个字节,会自动填充为8个字节

在这里插入图片描述

通过new A()创建一个对象的内存占用如下
1、整型成员变量a,占用4个字节
2、对象本身占用16个字节
那么创建该对象需要20个字节,由于“一般内存的使用,如果不够8个字节,会自动填充为8个字节”,所以创建该对象需要24个字节
Java中的数组被限定为对象,他们因为需要记录长度而需要额外的内存开销,一个数组一般需要24个字节的头信息(16个字节用于自己对象的开销+4个字节用于保存长度+4个字节填充)+保存值所需的内存

算法的空间复杂度
计算公式记作S(n)= O(f(n)),n为输入规模,f(n)为语句关于n所占存储空间的函数

案例
对指定数组元素进行反转,并返回反转内容

案例一:采用临时变量,将数组的第一位和最后一位互换位置,第二位和倒数第二位互换位置…

    public static void main(String[] args) {

       
        int a[] = {1, 2, 3, 4, 5};
        int temp;//申请4个字节
        for (int i = 0; i < a.length / 2; i++) {
            temp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = temp;
        }
        System.out.println(Arrays.toString(a));
    }

案例二:创建一个新的数组,数组的第一位是老数组的最后一位,数组的第二位是老数组的倒数第二位…

    public static void main(String[] args) {
        int a[] = {1, 2, 3, 4, 5};
        int resutl[] = new int[a.length];//申请4*n+24个字节
        for (int i = 0; i < a.length; i++) {
            resutl[i] = a[a.length - 1 - i];
        }
        System.out.println(Arrays.toString(a));
    }

案例一耗费了4个字节的空间
案例二耗费了4n+24个字节的空间

根据大O计法,案例有的空间复杂度为S(1),案例二的空间复杂度为S(n),所以从空间复杂度角度来看,案例一要优于案例二

由于java中内存垃圾回收机制,并且jvm对程序的内存也有优化(例如即时编译),我们无法精确的评估一个java程序的内存占用情况,但是了解了java的基本内存占用,使我们可以对java程序的内存占用情况进行估算

因为现在的机器内存都比较大,所以在默认情况下说的复杂度都是时间复杂度

如果是嵌入式设备开发,内存只有几个k,这个时候就需要对空间复杂度要求比较高了

原文链接:https://blog.csdn.net/lazy_cat_go/article/details/117569204


站长简介:前每日优鲜python全栈开发工程师,自媒体达人,逗比程序猿,钱少话少特宅,关注我,做朋友, 我们一起谈人生和理想吧!我的公众号:想吃麻辣香锅

关注公众号回复java,免费领取 免费领取java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

关注公众号回复java充值+你的账号,免费为您充值1000积分

0

1

2

3

4

5

6

7

8



所属网站分类: 技术文章 > 博客

作者:狗蛋来了

链接:http://www.javaheidong.com/blog/article/219618/f45a6ec573cd538f145f/

来源:java黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

9 0
收藏该文
已收藏

评论内容:(最多支持255个字符)