数据结构和算法概述

数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作相关问题的学科.

数据结构分类

逻辑结构分类

逻辑结构是从具体问题中抽象出来的模型,是抽象意义上的结构,按照对象中数据元素之间的相互关系分类,也是我们构面课题中需要关注和讨论的问题

a集合数据结构:集合数据中数据元素除了属于一个集合外,他们之间没有任何其的关系

b:线性结构:线性结构中的数据元素之间存在一对一的关系

c树形结构中的数据元素存在一对多的层次关系

d图形结构 的数据元素是多对多的关系

物理结构分类

逻辑结构在计算机中真正的表达方式为(又称为映像)称为物理结构,也可以叫存储结构.常见的物理结构有顺序存储结构,链式存储结构

顺序存储结构:

把数据元素放到地址连续的存储单元里,其数据的逻辑关系和物理关系是一直的,比如我们常用的数组就是顺序存储结构

访问速度快

顺序存储结构存在一定弊端,就像生活中排队时也会有人插队也有人可能会中途离开,这个整个结构都处于变化中,此时就需要链式存储结构

链式存储结构:

是吧数据元素存放在任意的存储单元里面,这组存储单元可以是连续的也可以是不连续的,此时,数据元素之间并不能互相反应元素间的逻辑关系,因此在链式存储结构中引进了一个指针存放数据元素的地址,这样通过地址就可以找到相关联的数据元素位置

查找效率低,但插入效率高

什么是算法

算法是阶梯方案的准确而完整的概述,是一系列解决问题的清晰指令,算法代表着用系统的方法解决问题的策略机制.也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出.

例如计算1-100的和

第一种解法

public class Main{

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

第二种解法

public class Main{

    public static void main(String[] args) {
        int b=100;
        int sum=(b+1)*b/2;
        System.out.println(sum);
    }
}

需求为2

10的阶乘

public static void main(String[] args) {
        System.out.println(result2(7));
    }
    public static int result(int data){
        if (data==1){
            return 1;
        }
        int result=data*result(data-1);
        return result;
    }
    public static int result2(int data){
        int result=1;
        for (int i=1;i<=data;i++){
            result=result*i;
        }
        return result;
    }

第一个函数会在执行完之后才数据才会出栈

算法的时间复杂度分析

事后分析估算法

在计算机程序编写钱,一句统计方法进行估算,经过总结,我们发现一个高级语言编写的程序在计算机上运行所消耗的时间取决于下列因素

1. 算法采用的策略和方案
2. 编译产生的代码质量
3. 问题的输入规模(所谓问题输入规模就是输入量的多少)
4. 机器执行指令的速度

由此可见,抛开这些与计算机软件有关的因素,一个程序的运行时间以来于算法的好坏和问题的输入规模.如果算法固定,那么该算法的执行时间就只和问题的输入规模有关系了.

我们一之前的案例进行分析第一种

执行了n次和一次的差距

重点

• 算法函数中n最高次幂越小,算法效率越高
• 算法函数中的常数可以忽略
• 算法函数中最高次幂越小,算法效率越高

大O记法

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进行分析T(n)随着n的变化情况并确定T(n)的量级.算法的时间复杂度,就是算法的时间量度,记做T(n)=O(f(n)).它表示随着问题规模增大,执行时间的增长率和f(n)的增长相同,称作算法渐进时间复杂度,简称时间复杂度,其中f(n)是问题规模n的某个函数

在这里我们需要明确一个事情:执行次数=执行时间

用大O()来体现算法时间复杂度的记法,我们称之为大O记法.一般情况下,随着输入规模n的增大,T(n)增长最慢的算法为最优算法.

给予我们对函数渐进增长的分析,推导大O阶的表示法有以下几个规则可以使用

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数中,只保留最高阶项
3. 如果最高阶项存在,且常数因子部位1,则去除这个项相乘的常数

比如

算法1,3次

算法2,n+3次

算法3:n^2+2次

大O计法分别为

算法1:O(1)

算法2:O(n)

算法3O(n^2)

常见的大O阶

线性阶 O(n)

平方阶O(n^2)

立方阶O(n^3)

对数阶级

对数阶

public static void main(String[] args) {
        int i=1,n=100;
        while (i<n){
            i=i*2;
        }
    }

每次i*2之后,就距离n更进一步,假设有x个2相乘后大于n则会退出循环.由于是2^x=n,得到x=log(2),所以这个循环的

时间复杂度为O(Logn),为什么不是O(Log2n)呢

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

常数阶

   public static void main(String[] args) {
        int n=100;
        int i=n+2;
        System.out.println(i);
    }

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

其他常见的时间复杂度总结

复杂程度从低到高为

O(1)<O(Lohn)<O(n)<O(n^2)<O(N^3)

时间复杂度一般是分析最坏的情况下代码运行的时间

空间复杂度分析

java中的空间占用

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

一个引用需要八个字节表示

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

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

public class Main{
    public int a=1;

}

通过new Main()创建一个对象的内存占用如下

1. 整形成员变量a占用4个字节
2. 对象本身占用16个字节

那么对象总共需要20个字节,但是由于不是以8为单位,会自动填充为24个字节

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

算法的空间复杂度

public class Main{

    public static void main(String[] args) {
        int a[]={1,2,3,4,5,6};
        a=reverse2(a);
        for (int i=0;i<a.length;i++){
            System.out.println(a[i]);
        }
    }
    public static int[] reverse1(int [] array){
        int len=array.length;
        int temp;
        for (int start=0,end=len-1;start<=end;start++,end--){
            temp=array[start];
            array[start]=array[end];
            array[end]=temp;
        }
        return array;
    }
    public static int [] reverse2(int [] array){
        int []temp=new int[array.length];
        for (int i=0;i<array.length;i++){
            temp[i]=array[array.length-i-1];
        }
        return temp;
    }
}

忽略判断条件的内存

解法1的空间复杂度为O(1)

解法2的空间复杂度为O(n)

由于java中有垃圾回收机制,并且java程序的内存占用也有优化,因此我们无法精确的评估一个java程序的内存占用情况,但是了解java 的基本内存占用,使我们可以对java程序的内存占用情况进行估算