Java数据结构与算法（一）：概述

一、概述

1.1 什么是数据结构

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。
一般来讲，数据结构是计算机组织、存储数据的方式。

1.2 数据结构分类

数据结构可以分为逻辑结构和物理结构两大类。
逻辑结构分类：
逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类。

• 集合结构
• 线性结构
• 树形结构
• 图形结构

物理结构分类：
逻辑结构在计算机中真正的表示方式（又称为映像）称为物理结构，也叫做存储结构。常见的物理结构有顺序存储结构、链式存储结构。

• 顺序存储结构：把元素放到地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的；
• 链式存储结构：把元素存放在任意的存储单元里，这组存储单元可以是连续的也可以是不连续的。此时，数据元素之间并不能反映元素之间的逻辑关系，因此链式存储结构中引入了一个指针存放数据元素的地址，这样通过指针就可以找到相关联数据元素的位置。

1.3 什么是算法？

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

二、算法分析

研究算法的目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求。有关算法时间耗费分析，称之为算法的时间复杂度分析，有关算法的空间耗费分析，称之为算法的空间复杂度分析。

2.1 时间复杂度

2.1.1 规律

• 算法函数中的常数可以忽略；
• 算法函数中最高次幂的常数因子可以忽略；
• 算法函数中最高次幂越小，算法效率越高。

2.1.2 大O记法

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

2.1.3 常见的大O阶

• 常数阶：O(1)
• 线性阶：O(n)
• 平方阶：O(n^2)
• 立方阶：O(n^3)
• 对数阶：O(logn)

2.1.4 最坏情况

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以除非特别指定，运行时间都指的是最坏情况下的运行时间。
例如：查找数组元素，期望的元素最后一个才查询到，那么时间复杂度为O(n)。

2.2 空间复杂度

空间复杂度也是使用大O记法，与时间复杂度类似。

• Java中常见的内存占用...
• 计算访问内存的方式都是一次一个字节
• 一个引用（机器地址）需要8个字节表示
• 创建一个对象，比如new Date()，除了Date对象内部存储的数据占用的内存，该对象本身也有内存开销，每个对象自身开销都是16个字节，用来保存对象的头信息
• 一般内存的使用，如果不够8个字节，都会被自动填充为8字节
• Java数组被限定为对象，一般都会因为记录长度而需要额外的长度，一个原始数据类型的数组一般需要24字节的头信息（16个自己的对象开销，4字节用于保存长度以及4个填充字节）再加上保存值所需要的内存

Java数据结构与算法（一）：概述

原文：https://www.cnblogs.com/hanyezzz/p/14010919.html