java数据结构学习笔记01

一、算法概述 （一） 什么是算法

算法（此处指计算机科学领域的算法），他的本质是一系列程序指令的，用于解决特定的运算和逻辑问题。

（二）算法好坏的衡量标准

1.时间复杂度
2.空间复杂度

（三）什么是数据结构

数据结构，是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

（四）数据结构的组成 1.线性结构

线性结构是最简单的数据结构，包括数组，链表，以及由它们衍生出来的栈、队列、哈希表。

2.树

树是相对复杂的数据结构，典型代表是二叉树，由他衍生出了二叉堆之类的数据结构。

3.图

图是更为复杂的数据结构，因为在图中会呈现出多对多的关联关系。

4.其他数据结构

除上述几种基本的数据结构外，还有一些由基本数据结构变形而来的，用于解决某些特定问题的数据结构，如：跳表、哈希链表、位图等。

（五）复杂度 1. 时间复杂度

时间复杂度简单来谁就是程序基本 *** 作次数（程序的相对执行时间）。
设T(n)为程序基本 *** 作执行次数的函数（也可以认为是程序的相对执行时间函数）n为输入规模。下面为4种常见的执行方式。
场景一: T(n) = 3n=O(n) 执行次数是线性的。

void test1 (int n) {
	for (int i = 0; i < n; i++ ) { 
	System.out.out.println(" 今天也要好好学习");
		}
	}

场景二： T(n) = 5 logn = O(logn)执行次数是用对数计算的。

void test2(int n) {
	for (int i = n; i >1; i /= 2 {
	System,out.println("好好学习java数据结构！");
		}
	}	

场景三：T(n) = 2= O(1)执行次数是常量。

void test3(int n) {
	System.out.println("今天你学习javal吗？");
	System.out.println("今天你敲代码了吗？");
    }

场景四:T(n) = 0.5nn + 0.5n =O(nn)，执行次数是用多项式计算的。

void test4 (int n) {
	for (int i = 0; i < n; i++;) {
		for(int j = 0; j < i; j ++;) {
			System.out.println("坚持");
			}
			System.out.println("java");
		}
	}

1) 渐进时间复杂度

(1)渐进时间复杂度的定义
如存在函数f(n),使得当n趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n) 是T(n)的同数量级函数。记作T(n) =O(f(n))，称为 O( f(n) ) ,O为算法的渐进时间复杂度，建成时间复杂度。
因为渐进时间复杂度用大写O来表示，所以也被称为大O表示法。

2)推导时间复杂度的原则

(1)原则

• 如果运行时间是常量级，则用常数1表示。
• 只保留时间函数中的最高阶项。
• 如果最高阶项存在，则省去最高阶项前面的系数。

(2)上述四种时间复杂度从小到大的排序
O(1) < O(logn) < O(n) < O(n*n)

2.空间复杂度

和时间复杂度类似，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，它同样使用了大O表示法。
常见的空间复杂度有以下几种情形。
1.常量空间
当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。

void func1 (int n) {
	int var = 3;
	...
	}

2.线性空间
当算法分配的空间是一个现行的集合（如数组），并且集合大小和输入规模n成正比时，空间复杂度记作O(n)。

void func2(int n) {
	int[] array = new int[n];
	...
	}

3.二维空间
当算法分配的空间是一个二维数组的集合，并且集合的长度和宽度都与输入的规模n成正比时，空间复杂度记作O（n*n)。

void func3(int n) {
int[][] matrix = new int [n][n];
...
}

4.递归
纯粹的递归 *** 作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是O(n)。

void func4(int n) {
if(n <= 1) {
	return;
	}
func4(n-1);
...
}

3.时间和空间的取舍

在绝大多数的情况下，时间复杂度更重要一些，我们宁可多分配一些内存空间，也要提升程序的执行速度。