数据结构之时间复杂度&&空间复杂度的计算

数据结构:计算机如何存储数据的问题。DS关心的是如何高效的进行数据的读写。

算法:在特定的数据集上(不关心怎么进行具体数据的读写),如何利用数据完成特定的功能。算法本质上就是一系列运算的先后集合。

那么,如何评价一个算法的好坏?

从两种维度进行:时间效率与空间效率

时间复杂度:主要衡量一个算法的运行速度(不是实际计算机的运行速度,是理论值,在所有计算机上通用的描述) 

空间复杂度:主要衡量一个算法正常执行所需要的额外空间大小,不是当前数据集本身占用的空间

所谓额外空间:为了解决这个问题,新开辟的内存大小

1. 时间复杂度

不是具体的时间,在计算机领域,其实是一个数学函数。

因为不同的计算机硬件不同,相同的算法在不同的CPU,内存这些硬件上具体的执行时间都会有差异,而且差异还挺大!

那么,利用数学函数,描述一个算法的基本操作的执行次数,就是所谓的时间复杂度

 在函数中,基本的执行语句可以不统计,基本语句和变量N毫无关系,时间复杂度看重的是执行次数和传入的变量之间的关系

使用大O渐进表示法(数学函数,表示渐进函数)来描述一个算法的时间效率。

1.1 推导大O阶的方法:

(1)用常数1来代替函数中的所有加法常数(只要是常量,常数,都会1,无论常量有多大,用1代替)

因为常数和传入数值N变量毫无关系,此算法是一个稳定的时间效率算法,和变量无关!

(2)只保留函数的最高阶项,所有的低阶省略不计

(3)若最高阶项存在且项数不为1,统一将其最高阶的项数看做1

先看最高阶在哪,低阶全部省略;若没有变量参与,统一都是常数1。

例如:F(N)=N^2+2N+10                  时间复杂度:F(N)=O(N^2)

1.2 时间复杂度评价标准

一个算法的时间复杂度存在最好、最坏、平均时间复杂度。

  • 最好:任意输入的数据,最小的执行次数(算法的下界)
  • 最坏:任意输入的数据,最大的执行次数(算法的上界)
  • 平均:任意输入的数据,平均的执行次数

eg:在长度为N的数组中,搜索一个数据x

最坏:若x刚好在数组的末尾或者不存在该数据,则需将整个数组进行遍历,执行N次才有结果

最好:若x刚好在数组首端,执行一次就能得到结果

平均:1+2+3+......+N=(1+N)*N/2(N个数据的总共查找次数)

           单个数据((1+N)*N/2)/N =N/2       时间复杂度:O(N)

衡量一个算法的时间复杂度取上界,即考虑算法的最坏情况,使用大O阶时间复杂度来描述最坏情况就是整个算法的时间复杂度。

1.3 相关例题

1. 大O阶看的是变量的最高阶,若存在多个输入变量,都需要保留各个变量的最高阶。

此时N和M都是变量,无法得知N和M谁大谁小,推导大O阶时,N和M都保留其最高阶。

时间复杂度:O(N+M)

2. N和循环次数没有关系,循环次始终为100。O(1) 和变量N无关

时间复杂度:O(1)

 3.  冒泡排序

循环次数为N^2,内外层都执行N次。时间复杂度:O(N^2)

 4. 二分查找

该循环每次不是从0--N,而是每次从区间的中间位置将区间一分为二,mid=N/2;

n/2+n/4+n/8+.....+n/16+....,要求这个执行次数,以2为底N的对数 

时间复杂度:O(logn)

 public static int binSearch(int[] arr,int value){
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int mid=(right+left)/2;
            if(value<arr[mid]){
                right=mid-1;
            }else if(value>arr[mid])
            {
                left=mid+1;
            }else{
                return mid;
            }
        }
        //抛出运行时异常,代表未找到元素(不能返回-1,因为-1也有可能为元素本身)
        throw new NoSuchElementException("没有找到该元素!");
    }

(1)原则:忽略底数(换底公式:无论底数为多少,都可以换成以10为底的)

O(logn)==>忽略底数,即:对数级别的时间复杂度

如果一个算法能够做到对数级别的时间复杂度,则是非常优秀的!

(2)如何分析一个算法是对数级别的时间复杂度?

若算法是不断的将一个变量除以一个常数:N/2,或者N/3,一直除到为1或者0,则这个算法一定是对数级别的算法O(logn),也叫折纸算法

(3)分析O(N)、O(logN)、O(N^2)随着N的不断变化,三个不同函数的变化趋势。

 二分查找在一亿的有序集合中,最坏只需要29次就能查到特定元素。

5. 关于递归算法的执行时间分析

public static int fibo(int N){
        return N<=2? N:fibo(N-2)+fibo(N-1);
    }

执行次数:将fibo函数展开,执行次数就是下图中的方框个数,也就是说,求执行次数就是求结点的总个数。 

2+4+6+8+....+..... 求二叉树的节点个数2^N+1==> 时间复杂度:O(2^N)

 public static int factor(int N){
        //1.base case
        if(N<=2){
            return N;
        }
        return N*factor(N-1);
    }

 执行次数:上述代码展开类比为:for(int i=1;i<N;i++){ int n*=i;},因此,时间复杂度为O(N)

总结:看一个递归算法的时间复杂度,就看递归展开,函数的执行次数即可!

2. 空间复杂度 

 算法执行过程中,额外开辟的空间大小。

时间复杂度描述的是算法的执行次数;

空间复杂度描述的是一个算法额外开辟的临时变量个数,也是使用大O渐进表示法。

eg:冒泡排序的空间复杂度O(1),额外开辟了一个临时变量temp。

2.1 分析空间复杂度

1. 斐波那契函数的空间复杂度

 public static int[] fibo(int N){
        int[] ret=new int[N+1];
        ret[0]=1;
        ret[1]=1;
        for (int i = 2; i<=N ; i++) {
            ret[i]=ret[i-1]+ret[i-2];
        }
        return ret;
    }

 由于函数中出现了new int[N+1];也就是说额外开辟了一个新数组,因此空间复杂度为O(N)。

2. 递归函数的空间复杂度

对于递归函数来说,每执行一次函数,就会在系统栈上产生新的栈帧,这就属于临时空间。

 public static int factor(int N){
        return N<=2?N:N*factor(N-1);
    }

也就是说观察其展开的次数。

空间复杂度:O(N)

总结:

非递归:空间复杂度就是看函数内部new了什么

递归:看函数的展开次数,每次调用一次函数,都会额外在栈上开辟栈帧空间。

一般空间复杂度最常见的为O(1)或O(N)

在题目中,出现空间复杂度要求为O(1),代表此时不能开辟新的数组且不能使用递归。