您现在的位置是:首页 > 正文

时间复杂度 和空间复杂度的计算

2024-02-01 04:32:09阅读 2

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

一般情况下,算法中基本操作重复执行的次数是问题规模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

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]+" ");
    }

冒泡排序的复杂度, 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);
    }
}

二分法的计算方式不断取数组中点,判断需要值与中点的比值,选择合适的那一半。最坏的情况就是取到数组的边界值。此时
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 次计算,所以同样进行log2n次赋值,所以空间复杂度为log2n

在 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;
}

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

网站文章

  • Java语言----二叉树 最新发布

    Java语言----二叉树 最新发布

    二叉树详细讲解,以及Java实现代码

    2024-02-01 04:31:41
  • Error: Flutter plugin not installed; this adds Flutter specific functionality. - Flutter

    Error: Flutter plugin not installed; this adds Flutter specific functionality. - Flutter

    安装 Flutter 的时候在 Android Studio IED 处遇到了一些小的插件缺失问题,具体异常提示如下: [!] Android Studio (version 3.4) ✗ Flutter plugin not installed; this adds Flutter specific functionality. ✗ Dart plugin not insta...

    2024-02-01 04:31:36
  • TypeScript 使用let和const声明变量

    使用 let 声明变量 关键字 let 是 ES6 中新增的特性,它的出现是为了解决 var 变量声明所存在的一些问题,let 声明变量的语法和 var 的很像,例如: let a = 1; 其实 l...

    2024-02-01 04:31:27
  • 2020年大厂Java面试前复习的正确姿势(800+面试题答案解析)

    前言个人觉得面试也像是一场全新的征程,失败和胜利都是平常之事。所以,劝各位不要因为面试失败而灰心、 丧失斗志。也不要因为面试通过而沾沾自喜,等待你的将是更美好的未来,继续加油!本篇分享的面试题内容包括:Java、MyBatis、ZooKeeper、Dubbo、Elasticsearch、Redis、MySQL、Spring、SpringBoot、SpringCloud、RabbitMQ...

    2024-02-01 04:31:20
  • Spring,mysql,数据库连接池相关Jar包下载

    Spring,mysql,数据库连接池相关Jar包下载

    自己之前从网上下载使用的一些jar包。现在基本上使用maven导入依赖,所以jar包在网上找起来也很麻烦,自己整合了一些jar包放在网盘里,供下载。主要包括:1.spring-framework-5.0版本的所有jar包2.mysql-connector-java 5.x和8.x版本的jar包3.commons-logging-1.24.commons-beautils-1.945.c3...

    2024-02-01 04:30:52
  • html文章图文标题,什么是 WordPress 网站图片title标题/alt替代文本/caption说明/description图像描述标签?如何添加?...

    html文章图文标题,什么是 WordPress 网站图片title标题/alt替代文本/caption说明/description图像描述标签?如何添加?...

    什么是 WordPress 网站图片title标题/alt替代文本/caption说明/description图像描述标签?如何添加?当你浏览网站的时候,如果图片打不开,那么在图片位置出现文字提示,这...

    2024-02-01 04:30:47
  • nodejs的require()函数真正干了些啥?

    nodejs的require()函数真正干了些啥?

    首先应当知道,require函数是nodejs提供的,用来模块化的,内置函数。,其中包含了导入目标js文件中暴露的数据(属性、函数)。可以通过var obj = require(“./mydemo.js”);接收,通过obj.x,obj.func( )取用。,运行这个函数。但是,你不能我说啥就是啥啊,怎么验证呢?

    2024-02-01 04:30:39
  • 课程 | 混沌大学李善友第一性原理

    课程 | 混沌大学李善友第一性原理

    害怕,哈哈哈哈哈哈哈哈

    2024-02-01 04:30:10
  • Go语言学习-基本

    程序结构命名​ 如果是在函数外部定义,那么将在当前包的所有文件中都可以访问。名字的开头字母的大小写决定了名字在包外的可见性。如果一个名字是大写字母开头的(译注:必须是在函数外部定义的包级名字;包级函...

    2024-02-01 04:30:04
  • Trapping Rain Water

    Trapping Rain Water

    Givennnon-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.For example,Given[0,1,0,2,1,0,1,3,2,1,2,1], r...

    2024-02-01 04:29:57