初始数据结构☞复杂度与泛式

一.时间复杂度

定义：

算法的时间复杂度是一个数学函数，算法中的基本操作的执行次数，为算法的时间复杂度。

O渐进表示方法：

原因：

计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O 的渐进表示法。

举例练习：

// 计算func2的时间复杂度？
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}计算func3的时间复杂度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
}
// 计算func4的时间复杂度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
// 计算bubbleSort的时间复杂度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}
}
}
// 计算binarySearch的时间复杂度？
int binarySearch(int[] array, int value) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + ((end-begin) / 2);
if (array[mid] < value)
begin = mid + 1;
else if (array[mid] > value)
end = mid - 1;
else
return mid;
}
return -1;
}
// 计算阶乘递归factorial的时间复杂度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
// 计算斐波那契递归fibonacci的时间复杂度？
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

分析：

1. 实例 1 基本操作执行了 2N+10 次，通过推导大 O 阶方法知道，时间复杂度为 O(N)

2. 实例 2 基本操作执行了 M+N 次，有两个未知数 M 和 N ，时间复杂度为 O(N+M)

3. 实例 3 基本操作执行了 100 次，通过推导大 O 阶方法，时间复杂度为 O(1)

4. 实例 4 基本操作执行最好 N 次，最坏执行了 (N*(N-1))/2 次，通过推导大 O 阶方法 + 时间复杂度一般看最坏，时间复杂度为 O(N^2)

5. 实例 5 基本操作执行最好 1次，最坏 log（以2为低）n次，时间复杂度为 O(log（以2为低）n ) ps：在算法分析中表示是底数为 2 ，对数为 N ，有些地方会写成 lgN。

6. 实例 6 通过计算分析发现基本操作递归了 N 次，时间复杂度为 O(N) 。

7. 实例 7通过计算分析发现基本操作递归了2的n次方次，时间复杂度为O( 2的n次方)。

二.空间复杂度

定义：

空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大 O 渐进表示法 。

举例练习：

// 计算bubbleSort的空间复杂度？
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
boolean sorted = true;
for (int i = 1; i < end; i++) {
if (array[i - 1] > array[i]) {
Swap(array, i - 1, i);
sorted = false;
}
}
if (sorted == true) {
break;
}}}// 计算fibonacci的空间复杂度？
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}// 计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}

分析：

1. 实例 1 使用了常数个额外空间，所以空间复杂度为 O(1)

2. 实例 2 动态开辟了 N 个空间，空间复杂度为 O(N)

3. 实例 3 递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)

三.包装类

定义：

在 Java 中，由于基本类型不是继承自 Object ，为了在泛型代码中可以支持基本类型， Java 给每个基本类型都对应了一个包装类型。（为了让基本类型也面向对象）

基本类型=>包装类

byte Byte

short Short

int Integer

long Long

float Float

double Double

char Character

boolean Boolean

（除了 Integer 和 Character ，其余基本类型的包装类都是首字母大写。）

装箱与拆箱：

int i = 10 ;

// 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中

Integer ii = Integer . valueOf ( i );

Integer ij = new Integer ( i );

// 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中

int j = ii . intValue ();

注意：自动装箱：

Integer ii = i; // 自动装箱

Integer ij = (Integer)i; // 自动装箱

int j = ii; // 自动拆箱

int k = (int)ii; // 自动拆箱

注：

public static void main(String[] args) {
Integer a = 127;
Integer b = 127;
Integer c = 128;
Integer d = 128;
System.out.println(a == b);
System.out.println(c == d);
}
//true false

原因：在变量位于-128到125时是直接赋值，其他情况上就不是了

四.认识泛型

泛型的主要目的：

就是指定当前的容器，要持有什么类型的对象。让编译器去做检查。此时，就需要把类型，作为参数传递。需要什么类型，就传入什么类型。

语法：

class 泛型类名称<类型形参列表> {
// 这里可以使用类型参数
}
class ClassName<T1, T2, ..., Tn> {
}

class 泛型类名称<类型形参列表> extends 继承类/* 这里可以使用类型参数 */ {
// 这里可以使用类型参数
}
class ClassName<T1, T2, ..., Tn> extends ParentClass<T1> {
// 可以只使用部分类型参数
}

代码练习：

//实现一个类，类中包含一个数组成员，使得数组中可以存放任何类型的数据，也可以根据成员方法返回数
//组中某个下标的值？
class MyArray<T> {
public T[] array = (T[])new Object[10];//1
public T getPos(int pos) {
return this.array[pos];
}
public void setVal(int pos,T val) {
this.array[pos] = val;
}
}
public class TestDemo {
public static void main(String[] args) {
MyArray<Integer> myArray = new MyArray<>();//2
myArray.setVal(0,10);
myArray.setVal(1,12);
int ret = myArray.getPos(1);//3
System.out.println(ret);
myArray.setVal(2,"bit");//4
}
}

代码解释：

1. 类名后的 <T> 代表占位符，表示当前类是一个泛型类

了解： 【规范】类型形参一般使用一个大写字母表示，常用的名称有：

E 表示 Element

K 表示 Key

V 表示 Value

N 表示 Number

T 表示 Type

S, U, V 等等 - 第二、第三、第四个类型