时间复杂度 和空间复杂度的计算_时间复杂度和空间复杂度怎么算

一、 算法的时间复杂度定义

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 )，简称时间复杂度。

1、根据定义，可以归纳出基本的计算步骤
（1.）计算出基本操作的最坏情况执行次数T(n)

（2）计算出T(n)的数量级 （计算数量级只需要保留 最高次幂，并省略系数）
用f(n)=T(n)来表示函数

（3）用大O来表示时间复杂度 ，用O(省略系数的最高次幂)表示

常见时间复杂度：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

例子：

//hash的计算公式
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
//hash获取 数组位置
 tab[i = (n - 1) & hash
1
2
3
4
5
6
7
8

hashmap获取链表的位置的T（n）=2 循环的时间复杂度为O(1)

   public static void main(String[] args) {
        //冒泡排序算法
        int[] numbers=new int[]{1,5,8,2,3,9,4};
        int i,j;
        for(i=0;i<numbers.length-1;i++)   
        {
            for(j=0;j<numbers.length-1-i;j++)  
            {
                if(numbers[j]>numbers[j+1])  
                {
                    int temp=numbers[j];  //n*n  (属于基本操作)
                    numbers[j]=numbers[j+1];  //n*n  (属于基本操作)
                    numbers[j+1]=temp;  //n*n  (属于基本操作)
                }
            }
        }
        System.out.println("从小到大排序后的结果是:");
        for(i=0;i<numbers.length;i++)
            System.out.print(numbers[i]+" ");
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

冒泡排序的复杂度， T（n）= n^2 +n^2 +n^2，根据上面括号里的同数量级，我们可以确定 n^2为T（n）的同数量级

则有f（n）= n^2，然后根据T（n）/f（n）求极限可得到常数c

则该算法的 时间复杂度：T（n）=O（n^2)

//在数组a（有序的并且不含重复元素）中查找x，用二分查找
//low表示数组a的左端点，high表示右端点
//找到返回元素在数组中的下标，找不到返回-1
    public static int binary_search(int[] a,int low,int high,int value){
    if(low>high) return -1;
    int mid=low+((high-low)>>1);
    if(a[mid]==value){
        return mid;
    }else if (a[mid]<value){
        return binary_search(a,mid+1,high,value);
    }else {
        return binary_search(a,low,mid-1,value);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二分法的计算方式不断取数组中点，判断需要值与中点的比值，选择合适的那一半。最坏的情况就是取到数组的边界值。此时
2^T（n）=n T(n)=log2^n f（n）=log2^n ，循环的时间复杂度为O(logn)

二、 算法的空间复杂度定义
算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数，也是一种“渐进表示法”，这些所需要的内存空间通常分为“固定空间内存”（包括基本程序代码、常数、变量等）和“变动空间内存”（随程序运行时而改变大小的使用空间）

计算方式:
递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。

之前写计算时间复杂度的时候，对递归的二分法，做了书写。每一次递归都对所有变量进行了一次赋值，由我们对时间复杂度的分析，当我们计算到n需要log2^n 次计算，所以同样进行log2^{n次赋值，所以空间复杂度为log2}n

在 public static int binary_search(int[] a,int n,int x){
    int low=0;
    int high=n-1;
    while(low<=high){
        int mid=low+((high-low)>>1);
        if(a[mid]>x){
            high=mid-1;
        }else if (a[mid]<x){
            low=mid+1;
        }else {
        //在a[mid]==x的前提下进行判断，主要是判断目标值重复出现，修改mid值使mid值提前
            if ((mid==low)||(a[mid-1]!=x))return mid;
            else high=mid-1;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

这个是关于循环实现二分法，但因为 基本步骤里面数据变量值创建一次，所以空间复杂度为O（1）。