精华内容
下载资源
问答
  • 时间复杂度的表示使用大O的渐进表示法: 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中,只保留最高阶项。 3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大...

    时间复杂度:
    一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法
    的时间复杂度。
    时间复杂度的表示使用大O的渐进表示法:
    1、用常数1取代运行时间中的所有加法常数。
    2、在修改后的运行次数函数中,只保留最高阶项。
    3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
    空间复杂度:
    空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少
    bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践
    复杂度类似,也使用大O渐进表示法。
    线性表:
    线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结
    构,常见的线性表:顺序表、链表、栈、队列、字符串…
    线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物
    理上存储时,通常以数组和链式结构的形式存储。
    顺序表:顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
    在这里插入图片描述
    1.静态顺序表:使用定长数组存储。
    2. 动态顺序表:使用动态开辟的数组存储

    public interface ISequence {
        //在pos位置插入data
        boolean add(int pos,Object data);
        //查找关键字key 找到返回key的下标,没有返回-1;
        int search(Object key);
        //查找是否包含关键字key是否在顺序表当中(这个和search有点冲突)
        boolean contains(Object key);
        //得到pos位置的值
        Object getPos(int pos);
        //删除第一次出现的关键字key
        Object remove(Object key);
        //得到顺序表的长度
        int size();
        //打印顺序表
        void display();
        //清空顺序表以防内存泄漏
        void clear();
    }
    
    
    import java.util.Arrays;
    
    /**
     * Created with IntelliJ IDEA.
     * Description:
     * User:
     * Date: 2019-04-16
     * Time: 14:54
     */
    public class MySequenceImpl implements ISequence {
        private Object[]elem;
        private int usedSize;
        private static final int DEFAULT_SIZE = 10;
        public MySequenceImpl() {
            this.elem = new Object[DEFAULT_SIZE];
            this.usedSize = 0;
        }
        //判断是否是满的顺序表
        public boolean isFull(){
            if(this.usedSize==this.elem.length){
                return true;
            }
            return false;
        }
        //在pos位置加上data
        @Override
        public boolean add(int pos, Object data) {
            //判断pos的合法性
            if(pos < 0 || pos > this.usedSize) {
                return false;
            }
            //如果顺序表满,则将顺序表扩大为原来的二倍
            if(isFull()){
                this.elem = Arrays.copyOf(this.elem, this.elem.length*2);
            }
            //在pos位置加上data,挪数据,从后往前
            for (int i = this.usedSize-1; i >= pos ; i--) {
                this.elem[i+1] = this.elem[i];
            }
            this.elem[pos] = data;
            this.usedSize++;
            return true;
        }
        //判断是否为空
        public boolean isEmpty() {
            return this.usedSize == 0;
        }
    
        @Override
        public int search(Object key) {
            //需要判断顺序表是否为空
            if(key == null){
                return -1;
    
            }
            if (isEmpty()){
                throw new UnsupportedOperationException("顺序表为空");
            }
            for (int i = 0; i < this.usedSize; i++) {
                if (this.elem[i].equals(key)) {
                    System.out.println(i);
                    return i;
                }
    
            }
            return -1;
        }
    
        @Override
        public boolean contains(Object key) {
            if(key==null){
                return false;
            }
            if (isEmpty()){
                throw new UnsupportedOperationException("顺序表为空");
            }
            for (int i = 0; i < this.usedSize; i++) {
                if (this.elem[i].equals(key)) {
                    return true;
                }
            }
            return false;
        }
    
        @Override
        public Object getPos(int pos) {
            if(pos < 0 || pos >= this.usedSize || isEmpty()){
                return null;
            }
            return this.elem[pos];
        }
        //删除第一次出现的关键字key
        //删除之前,保存需要删除的值作为返回值
        @Override
        public Object remove(Object key) {
            int index = search(key);
            if(index == -1) {
                return null;
            }
            //将要删除的值保存下来
            Object oldData = this.elem[index];
            int i = 0;
            //将key删除后,后面的值往前一位挪
            for (i = index; i < this.usedSize-1; i++) {
                this.elem[i] = this.elem[i+1];
            }
            this.elem[i+1] = null;
            this.usedSize--;
            return oldData;
        }
    
        @Override
        public int size() {
            return this.usedSize;
        }
    
        @Override
        public void display() {
            for (int i = 0; i <this.usedSize ; i++) {
                System.out.println(this.elem[i]+" ");
            }
            System.out.println();
        }
    
        @Override
        public void clear() {
            for (int i = 0; i <this.usedSize ; i++) {
                this.elem[i]=null;
            }
            this.usedSize = 0;
        }
    }
    
    
    展开全文
  • 算法时间复杂度T(n)大小顺序

    万次阅读 2015-10-08 18:28:23
    一般情况下,算法中基本操作重复执行次数是问题规模n某个函数f(n),算法时间度量记作 T(n)=O(f(n)) ,他表示随问题规模n增大,算法执行时间增长率和f(n)增长相同,称作算法渐进时间复杂度(asymptotic...

     一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作 T(n)=O(f(n)) ,他表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长相同,称作算法的渐进时间复杂度(asymptotic time complexity),简称时间复杂度

        时间复杂度T(n)按数量级递增顺序为:

    常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 …… K次方阶 指数阶
    O(1) O(log2n) O(n) O(nlog2n) O(n2) O(n3) O(nk) O(2n)

    复杂度低 ---->---->---->---->---->---->---->---->---->---->---->---->----> 复杂度高

    展开全文
  • 常见的时间复杂度按照从低到高的顺序,包括O(1)、O(logn)、O(n)、O(nlogn)、O(n^2) 由于受运行环境和输入规模影响,代码绝对执行时间是无法预估。但我们却可以预估代码基本操作执行次数。 设T(n)为程序基本...

    在实际开发中,通常会选择以空间换时间。

    1. 时间复杂度:是对一个算法运行时间长短的量度,用大O表示,记作T(n)=O(f(n))。
      常见的时间复杂度按照从低到高的顺序,包括O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)

      • 由于受运行环境和输入规模的影响,代码的绝对执行时间是无法预估的。但我们却可以预估代码的基本操作执行次数。
      • 设T(n)为程序基本操作执行次数的函数(也可以认为是程序的相对执行时间函数),n为输入规模,以下场景为程序中最常见的4种执行方式:
        • 场景1: T(n)=3n, 执行次数是线性的。
          void eat1(int n){
          	for(int i=0; i<n; i++){
          		System.out.println("等待1分钟");
          		System.out.println("等待1分钟");
          		System.out.println("吃1cm面包");
          }}
          
        • 场景2: T(n)=5logn,执行次数是用对数计算的。
          void eat2(int n){
          	for(int i=n; i>1; i/=2){
          		System.out.println("等待1分钟");
          		System.out.println("等待1分钟");
          		System.out.println("等待1分钟");
          		System.out.println("等待1分钟");
          		System.out.println("吃一半面包");
          	}}
          
        • 场景3: T(n)=2,执行次数是常量。
          void eat3(int n){
          	System.out.println("等待1分钟");
          	System.out.println("吃1个鸡腿");
          }
          
        • 场景4: T(n)=0.5n^2+0.5n,执行次数是用多项式计算的。
          void eat4(int n){
          	for(int i=0; i<n; i++){
          		for(int j=0; j<i; j++){
          			System.out.println("等待1分钟");
          		}
          		System.out.println("吃1cm面包");}
          	}
          
      • 如何推导出时间复杂度呢?
        • 如果运行时间是常数量级,则用常数1表示
        • 只保留时间函数中的最高阶项
        • 如果最高阶项存在,则省去最高阶项前面的系数
        • 由以上规则推出:
          • 场景1: T(n)=O(n)
          • 场景2: T(n)=O(logn)
          • 场景3: T(n)=O(1)
          • 场景4: T(n)=O(n^2)
    2. 空间复杂度:是对一个算法在运行过程中临时占用存储空间大小的量度,用大O表示记作S(n)=O(f(n))
      常见的空间复杂度按照从低到高的顺序,包括O(1)、O(n)、O(n^2)。其中递归算法的空间复杂度和递归深度成正比

      • 常见的空间复杂度有下面几种情形:
        • 常量空间:当算法的存储空间大小固定,和输入规模没有直接的关系时,空间复杂度记作O(1)。
          void fun1(int n){
          	int var=3;
          	...
          }
          
        • 线性空间:当算法分配的空间是一个线性的集合(如数组),并且集合大小和输入规模n成正比时,空间复杂度记作O(n)
          void fun2(int n){
          	int[] array=new int[n];
          	...
          }
          
        • 二维空间:当算法分配的空间是一个二维数组集合,并且集合的长度和宽度都与输入规模n成正比时,空间复杂度记作O(n^2)
          void fun3(int n){
          	int[][] matrix=new int[n][n];
          	...
          }
          
        • 递归空间:递归是一个比较特殊的场景。虽然递归代码中没有显式地声明变量或集合,但是计算机在执行程序时,会专门分配一块内存,用来存储“方法调用栈”。“方法调用栈”包括进栈和出栈两个行为。当进入一个新方法时,执行入栈操作,把调用的方法和参数信息压入栈中。当方法返回时,执行出栈操作,把调用的方法和参数信息从栈中弹出。由出入栈的过程可以看出,执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的,如果递归的深度是n,那么空间复杂度就是O(n)。
          void fun4(int n){
          	if(n<=1){
          		return;
          	}
          	fun4(n-1);
          	...
          	}
          
    展开全文
  • 时间复杂度和空间复杂度是度量算法效率的常用指标 时间度量 事后统计,不常用 事前统计影响因素: 算法策略 问题规模 程序语言 代码质量 机器执行指令的速度 撇开软硬件的影响,算法运行工作量的大小只依赖...

    时间复杂度和空间复杂度是度量算法效率的常用指标

    时间度量

    1. 事后统计,不常用
    2. 事前统计影响因素:
      算法策略 问题规模 程序语言 代码质量 机器执行指令的速度

    撇开软硬件的影响,算法运行工作量的大小只依赖于问题的规模(通常用整数n表示)
    一个算法是由控制结构(顺序,分支,循环三种)和原操作(指固有数据类型的操作)构成,则算法时间取决于两者的综合效果。

    为了便于比较同一问题的不同算法,通常从算法中选取一种对于所研究问题来说是基本操作的原操作,以该基本操作重复执行的次数作为算法的时间度量。
    算法的时间复杂度记做 T(n)=O(f(n))
    它表示随问题规模n的增大,算法执行时间的增长率和 f(n) 的增长率相同

    原操作的执行次数与包含他的语句的执行次数相同

    • {++x; s = 0; }
    • for( i = 1 ; i <= n ; ++i ) { ++x ; s += x;}
    • for( j = 1 ; j <= n ; ++j )
      for( k = 1 ; k <= n ; ++k ) { ++x ; s += x;}

    含基本操作“x+1”的语句的频度分别为1,n和n^2,所以这三个程序段的时间复杂度分别为O(1)、O(n)、O( n^2 ) ,分别称为常量阶,线性阶和平方阶。

    有些情况下,算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在冒泡排序算法中,“交换序列中相邻两个整数”这个基本操作执行次数可能为0,或者O(n^2)。这类算法时间复杂度有两种表示方法:一是考虑所有情况下时间复杂度的期望值(麻烦,而且出现概率难确定,所以不常用);另一种是以最坏的情况下的时间复杂度作为该算法的时间复杂度。

    时间复杂度并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。也就是说,对于高速处理数据的计算机来说,处理某一个特定数据的效率不能衡量一个程序的好坏,而应该看当这个数据的规模变大到数百倍后,程序运行时间是否还是一样,或者也跟着慢了数百倍,或者变慢了数万倍。不管数据有多大,程序处理花的时间始终是那么多的,我们就说这个程序很好,具有O(1)的时间复杂度,也称常数级复杂度;数据规模变得有多大,花的时间也跟着变得有多长,这个程序的时间复杂度就是O(n),比如找n个数中的最大值;而像冒泡排序、插入排序等,数据扩大2倍,时间变慢4倍的,属于O(n^2) 的复杂度。还有一些穷举类的算法,所需时间长度成几何阶数上涨,这就是O(a^n) 的指数级复杂度,甚至O(n!)的阶乘级复杂度。

    空间复杂度

    S(n)=O(f(n))
    存储空间,工作空间(计算等),辅助存储空间等
    空间复杂度感觉不怎么常用。。。不研究了。。。。

    参考文献:《数据结构》 严蔚敏,吴伟民编著
    参考链接:http://www.matrix67.com/blog/archives/105

    展开全文
  • 算法,就是解决问题...(称为“时间复杂度”) 运行算法所需内存空间大小。(称为“空间复杂度”) 一个算法是由控制结构(顺序、分支和循环3种)和原操作(指固有数据类型操作)构成,则算法时间取决于两...
  • 算法时间复杂度T(n)大小顺序 时间复杂度 T(n) = O(F(n)) 算法时间复杂度T(n)大小顺序->: 常阶数 对数阶 线性阶 平方阶 立方阶 T(1) T(log2n) T(n) T(n^2) T(n^2) 个人简概:一行代码执行了多少次 1.T(1)...
  • 前言:为什么会出现时间复杂度这个概? 我们在编写代码时候为了完成一个函数功能,可能用到不同处理方式:顺序多... 时间复杂度概念:我们把 算法需要执行运算次数 用 输入大小n 函数 表示,即 T(n) 。此...
  • 最近,笔者学习了冒泡排序,在此简单分享一下。冒泡排序原理:对于一个数组,...如果有n个元素,则第一次循环进行n-1次,第二次循环进行n-2次,…………,第n-j次循环过后,会按大小顺序排出j个较大数。持续以上...
  • 哈希算法就是典型O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突话) 1.代码如下: #include<iostream> using namespace std; #define MaxSize 100 typedef struct { int ...
  • 在一组嵌套循环内部,一条语句的总运行时间为该语句的运行时间乘以该组所有的for循环的大小乘积。 法则3——顺序语句 求和即可 法则4——if/else 语句 if/else语句永远不超过判断的运行时间再加上s1(if后语句),s2...
  • 利用计数排序法,设置一大小为65536int数组,范围a[0]~a[65535],并初始为0,然后遍历n个数,假设这n个数在数组array[0...n-1]中,则i取值从0到n-1同时执行a[array[i]]++,最后再依照顺序读数组a,遇到不为0时,将...
  • 冒泡排序只在相邻元素大小不符合要求时才调换他们位置, 它并不改变相同元素之间相对顺序, 因此它是稳定排序算法. 由于冒泡排序中只有缓存temp变量需要内存空间, 因此空间复杂度为常量O(1). 最坏情况是每次...
  • 其所消耗时间大小顺序为O(1) < O(logn) < O(n) < O(n^2) < O(2^n)。 这里博主附图一张对各个式子做解释:注意时间复杂度只取对于表达式中最高次幂,除了最高次幂,其他都可以省略掉 二.空间
  • 逆序:在一个排列中,如果一对数前后位置与大小顺序相反,即前面数大于后面数,那么它们就称为一个逆序。 一、暴力做法 int count(int *a, int n) { int res = 0; for (int i=0; i<n-1; ++i) { for ...
  • 汉诺塔问题和其时间复杂度

    千次阅读 2018-10-12 09:35:13
    大梵天创造世界时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子...
  • 首先,排序算法稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等数其在序列前后位置顺序和排序后它们两个前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置...
  • 在一个排列中,如果一对数前后位置与大小顺序相反,即前面数大于后面数,那么它们就称为一个逆序。一个排列中逆序总数就称为这个排列逆序数。逆序数为偶数排列称为偶排列;逆序数为奇数排列称为奇...
  • 从里向外分析这些循环,在一组嵌套循环内部的一条语句的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。 法则3——顺序语句 将各个语句的运行时间求和即可。 法则4——if/else语句 一个if/else...
  • 利用计数排序法,设置一大小为65536int数组,范围a[0]~a[65535],并初始为0,然后遍历n个数,假设这n个数在数组array[0...n-1]中,则i取值从0到n-1同时执行a[array[i]]++,最后再依照顺序读数组a,遇到不为0时,将...
  • 在一个排列中,如果一对数前后位置与大小顺序相反,即前面数大于后面数,那么它们就称为一个逆序。一个排列中逆序总数就称为这个排列逆序数。现在给定一个序列,其中元素皆为整数(当然,这里只是为了方便...
  • 原理:将数组分为无序区和有序区两个区,然后不断将无序区第一个元素按大小顺序插入到有序区中去,最终将所有无序区元素都移动到有序区完成排序。 要点:设立哨兵,作为临时存储和判断数组边界之用。 实现: ...
  • 基于图像复杂度SAD计算的H.264全搜索快速算法黎仁国【期刊名称】《绵阳师范学院学报》【年(卷),期】2009(028)011【摘要】针对H.264...即把一个宏块划分为16个4×4的子块,根据这些子块的亮度复杂度的大小顺序依次计算...
  • 因为要求时间复杂度为O(N),所以不可以两层循环挨个比较,需要借助一块辅助空间,定义一个256大小的数组arr,将字符转化为assic码值作为下标。然后遍历统计数量等于二。 注意第二次遍历查找字符串中第一个只出现...
  • 算法思想归并排序主要思想是分治法,排序方法就是按照大小顺序合并两个元素,接着依次按照递归返回顺序,不断地合并排好序子数组,直到最后把整个数组顺序排好。主要过程是:将n个元素从中间切开,...
  • (a)设计一个时间复杂度优于O(n^2)的算法,其中n是数组a的大小,这意味着不列出所有的分数,代价为O(n^2)。对算法进行了分析,并使用顺序表示法给出了结果。 (b)在Python中以函数的形式实现算法: def kth_smallest_...
  • 按照元素入栈顺序,将要入栈第一个元素,同时压入两个栈中。后续每个元素入栈时,与sMin栈中栈顶元素比较大小,若入栈元素data 小于sMin栈顶元素,则把data同时压入两个栈中,若data大于sMin栈中栈顶元素,则只压...
  • 简单排序算法时间空间复杂度分析及应用-冒泡排序  冒泡排序算法,我上大学一开始...算法会比较节点前后节点,然后根据节点大小和排序顺序来决定这个节点前后节点是否交换,当循环终结后,就能得到排序想要结果

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 769
精华内容 307
关键字:

时间复杂度的大小顺序