数据结构1-复杂度与泛型

一.时间复杂度

（1）时间复杂度与执行次数成正比

（2）采用大O阶表示法

<1>用1来表示所有常数

<2>只保留最高阶项

<3>如果最高阶存在且系数不是1，要去掉系数，得到的结果就是大O阶

<4>大O阶需要算最坏情况

（3）时间复杂度循环案例计算

<1>题目1

<2>题目2

<3>题目3

<4>题目4

<5>题目5

<6>题目6

（4）时间复杂度递归案例计算

<1>求n的阶乘递归

<2>斐波那契数递归

二.空间复杂度

（1）计算的是变量的个数

（2）采用大O阶表示法

（3）空间复杂度循环案例计算

<1>题目一

只有数组一个变量，且没有存起来，所以为O(1)

<2>题目2

（4）空间复杂度递归案例计算

三.泛型

（1）泛型在jdk5引入

（2）装箱

<1>显示装箱

<2>隐式装箱

系统帮你装箱

（3）拆箱

（4）泛型的应用

（5）注意点

<1>间括号里用包装类型

<2>是一种编译机制，运行时没有泛型概念，即JVM虚拟机没有泛型

<3>画图理解

（6）泛型的上界

<1>可以实现接口

<2>可以继承一些包装好的类

四.泛型的编译机制->擦除机制

(1)图1

（2）图2