数据结构概念
逻辑结构
- 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
- 线性结构：数据元素之间是一对一的关系
- 树形结构：树形结构中元素之间存在一种一对多的层次关系
- 图形结构：元素是多对多的关系
物理结构（存储结构）
- 顺序存储：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
- 链式存储：把数据元素存放在任意存储单元里，这组存储单元可以是连续的，也可以是不连续的，通过指针找到下一个存放的地址
算法概念
- 假设现在要写一个求1+2+3+4+…..+100的程序
int num = 0;
for (int i=1;i<=100;i++){
num+=i;
}
System.out.println(num);
- 上面算法需要循环100次，当要求加到100000时，循环次数越多计算结果越慢，而采用高斯算法
int sum = 0, i = 1000000;
sum = (1 + i) * i / 2;
System.out.println(sum);
yBeXK.png
算法效率度量方法
- 事后度量法：通过计算算法开始时间与结束时间
- 事前分析估算法：分析程序执行代码次数（行数），优秀的算法相比普通算法根据问题输入规模 n 的大小，随着 n 的值越大，时间效率上的差异就越大
函数的渐进增长
- 假设有算法A与算法B：
- 算法A----要做2n+3次操作（如执行完一个n次的循环，然后又执行一个n次的循环，最后执行3次赋值运算）
- 算法B----要做3n+1次操作
- 当 n>2 时，算法A就开始优于算法B，随着时间增加，算法A比算法B越来越好
- 在实际算法变化中，我们常忽略这些加法常数
算法时间长度
推导大O的方法
- 用常数1取代运行时间中所有加法常数
- 在修改后的运行次数函数中，只保留最高阶项
- 如果最高阶项存在且不是为1，则去除常数项
常数阶
- 该算法运行次数为 f(n) = 3，根据推到大O方法，将常数项3改为1，该算法时间复杂度为 O(1)
int sum = 0, i = 1000000; /*执行一次*/
sum = (1 + i) * i / 2; /*执行一次*/
System.out.println(sum); /*执行一次*/
线性阶
- 确定算法的阶次，分析算法的复杂度，关键是分析循环结构的运行情况，下面代码时间复杂度为 O(n)，因为循环体中的代码要执行 n 次
int i,n =100;
for (i=0;i<n;i++){
//....
}
对数阶
- 下面代码每次会执行直到 count > n，每次执行完 count 会乘以 2，得 2的x次方=n 得到 x=log2n，该循环复杂程度为O(logn)
int count = 1;
while(count < n){
count = count * 2;
/* 时间复杂度为 O(1) 的程序步骤序列 */
}
平方阶
- 单个循环时间复杂度为 O(n)，而在循环嵌套内两个循环都执行 n ，则为 O(n的2次方)，如下面代码
int i,j,n = 200;
for(i = 0;i < n;i++){
for（j = 0;j < n;j++）{
// 时间复杂度为平方阶 O(n的2次方)
}
}
- 若外循环次数为m，内循环次数为n，则时间复杂度为 O(m*n)
int i, j, m = 300, n = 200;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
// 时间复杂度为 O(m*n)
}
}
- 下面代码调用了一个函数，函数的时间复杂度为O(1)，所以整体时间复杂度为O(n)
public static void main(String[] args){
int i,n = 200;
for(i = 0;i < n;i++){
fun();
}
}
public static void fun(){
System.out.println();
}
常见的时间复杂度
- 复杂度大小顺序为：O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方) < O(n的立方) < O(2的n次方) < O(n!) < O(n的n次方)
| 执行次数函数 |
阶 |
非正式术语 |
| 12 |
O(1) |
常数阶 |
| 2n+3 |
O(n) |
线性阶 |
| 3*(n平方)+2n+1 |
O(n的平方) |
平方阶 |
| 5log2n+20 |
O(logn) |
对数阶 |
| 2n+3nlog2n+19 |
O(nlogn) |
nlogn阶 |
| 6n的3次方+2n的平方+3n+4 |
O(n的立方) |
立方阶 |
| 2的n次方 |
O(2的n次方) |
指数阶 |
网友评论