一.时间复杂度
定义：
算法的时间复杂度是一个数学函数，算法中的基本操作的执行次数，为算法的时间复杂度。
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
等等
-
第二、第三、第四个类型
2.注释
1
处，不能
new泛型类型的数组
T
[]
ts
=
new
T
[
5
];
//
是不对的
3.
注释
2
处，类型后加入
<Integer>
指定当前类型
4.
注释
3
处，不需要进行强制类型转换
5.
注释
4
处，代码编译报错，此时因为在注释
2
处指定类当前的类型，此时在注释
4
处，编译器会在存放元素的时
候帮助我们进行类型检查。
