美文网首页
day01_时间,空间复杂度

day01_时间,空间复杂度

作者: 蹦蹦跶跶的起床啊 | 来源:发表于2020-02-27 21:17 被阅读0次

数据结构概述

一个优秀的算法追求以下两个目标:
1.花最少的时间完成需求;
2.占用最少的内存空间完成需求;

算法分析

算法时间复杂度分析

事后分析方法(不建议)

long start = System.currentTimeMillis();
long end = System.currentTimeMillis();
采用如上结束时间减去开始时间来计算程序运行时间, 中间写的是测试整个程序需要运行的所有代码.

硬件会影响最终计算的时间, 如果程序内容过于庞大,写的测试代码也容易出错

事前分析方法

程序在计算机上运行所消耗的时间取决于下列因素:
1.算法采用的策略和方案;(可干预)
2.问题的输入规模(所谓的问题输入规模就是输入量的多少);(可干预)
3.编译产生的代码质量;(软件本身决定)
4.机器执行指令的速度;(硬件本身决定)

我们分析一个算法的运行时间,最重要的就是把核心操作的次数和输入规模关联起来。
随着输入规模的增大,算法的常数操作可以忽略不计
随着输入规模的增大,与最高次项相乘的常数可以忽略
最高次项的指数大的,随着n的增长,结果也会变得增长特别快
算法函数中n最高次幂越小,算法效率越高

总结:
1.算法函数中的常数可以忽略;
2.算法函数中最高次幂的常数因子可以忽略;
3.算法函数中最高次幂越小,算法效率越高。

时间复杂度

程序的执行次数== 执行时间

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

大O推导法则

推导大O阶的表示法有以下几个规则可以使用:
1.用常数1取代运行时间中的所有加法常数;
2.在修改后的运行次数中,只保留高阶项;
3.如果最高阶项存在,且常数因子不为1,则去除与这个项相乘的常数;
比如算法一: 执行了3次, 则表示为O(1);
执行了n+3次 ,则表示为O(N);
执行了n^2+2次, 则表示为O(n^2);

常见的大O阶

1.线性阶
一般含有非嵌套循环涉及线性阶,线性阶就是随着输入规模的扩大,对应计算次数呈直线增长,
如:

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

上述代码循环的时间复杂度为O(n),因为循环体中的代码需要执行n次

2.平方阶
一般嵌套循环属于这种时间复杂度
如:

int sum=0,n=100;
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=n ; j++) {
                sum+=i;
            }
        }

上述代码总共程序想要从这两个循环中出来,就需要执行100*100次,也就是n的平方次,所以这段代码的时间复杂度是O(n^2).

3.立方阶
一般三层嵌套循环属于这种时间复杂度

int x=0,n=100;
        for (int i = 1; i <=n ; i++) {
            for (int j = i; j <=n ; j++) {
                for (int j = i; j <=n ; j++) {
                    x++;//核心代码执行100*100*100次
                }
            }
        }

总共程序想要从这三个循环中出来,就需要执行100100100次,也就是n的立方,所以这段代码的时间复杂度是O(n^3).

4.对数阶

int i=1,n=100;
while(i<n){
    i = i*2;//核心代码
}

由于每次i*2之后,就距离n更近一步,假设有x个2相乘后大于n,则会退出循环。由于是2^x=n,得到x=log(2)n,所
以这个循环的时间复杂度为O(logn);

对于对数阶,由于随着输入规模n的增大,不管底数为多少,他们的增长趋势是一样的,所以我们会忽略底数

5.常数阶

     int n=100;
     int i=n+2;

不管输入规模n是多少,都执行2次,根据大O推导法则,常数用1来替换,所以上述代码的时间复杂度为O(1)

常见大O阶时间复杂度

他们的复杂程度从低到高依次为:
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2 )<O(n^3)
如果说时间复杂度高于O(n^2)都要考虑对算法进行优化

函数调用过程中时间复杂度的分析

public static void main(String[] args) {
    int n=100;
    show(n);
    for (int i = 0; i < n; i++) {
        show(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println(j);
        }
    }
}
 
private static void show(int i) {
    for (int j = 0; j < i; i++) {
        System.out.println(i);
    }
}

在show方法中,有一个for循环,所以show方法的时间复杂度为O(n),在main方法中,show(n)这行代码内部执行的次数为n,第一个for循环内调用了show方法,所以其执行次数为n^2,第二个嵌套for循环内只执行了一行代码,
所以其执行次数为n^2 ,那么main方法总执行次数为n+n2+n2=2n^2+n 。根据大O推导规则,去掉n保留最高阶项,并去掉最高阶项的常数因子2,所以最终main方法的时间复杂度为O(n^2)

最坏情况时间复杂度

public int search(int num){
    int[] arr={11,10,8,9,7,22,23,0};
    for (int i = 0; i < arr.length; i++) {
        if (num==arr[i]){
            return i;
        }
    }
    return -1;
}

最好情况:
查找的第一个数字就是期望的数字,那么算法的时间复杂度为O(1)
最坏情况:
查找的最后一个数字,才是期望的数字,那么算法的时间复杂度为O(n)
平均情况:
任何数字查找的平均成本是O(n/2)
最坏情况是一种保证,在应用中,这是一种最基本的保障,即使在最坏情况下,也能够正常提供服务,所以,除非特别指定,我们提到的运行时间都指的是最坏情况下的运行时间。

算法空间复杂度分析(一般默认求得是时间复杂度)

java中常见的内存占用

1.基本类型内存占用


2.计算机访问内存的方式都是一次一个字节


3.一个引用(机器地址)需要8个字节表示:
例如: Date date = new Date(),则date这个变量需要占用8个字节来表示

4.创建一个对象,比如new Date(),除了Date对象内部存储的数据(例如年月日等信息)占用的内存,该对象本身也
有内存开销,每个对象的自身开销是16个字节,用来保存对象的头信息。

5.一般内存的使用,如果不够8个字节,都会被自动填充为8字节:


6.java中数组被被限定为对象,他们一般都会因为记录长度而需要额外的内存,一个原始数据类型的数组一般需要
24字节的头信息(16个自己的对象开销,4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

空间复杂度计算

S(n)=O(f(n))
计算如下:

public static int[] reverse2(int[] arr){
    int n=arr.length;//申请4个字节
    int[] temp=new int[n];//申请n*4个字节+数组自身头信息开销24个字节
    for (int i = n-1; i >=0; i--) {
        temp[n-1-i]=arr[i];
    }
    return temp;
}

相关文章

网友评论

      本文标题:day01_时间,空间复杂度

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