算法定义：
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，每个指令表示一个或多个操作。（简单理解：解决问题的方法）
算法特性：
- 输入输出：至少有一个数据输入，有计算的结果输出
输入是为了确立初始条件，也可以没有 - 有穷性：在有限的执行次数和执行时间下得到结果
- 确定性：不同的输入要有确定的输出结果，且结果不可以有二义性
- 可行性：每一句代码都是可执行的，在有限步骤内完成
在哪些方面去衡量？
- 正确性
是否获得正确的结果 - 可读性
算法阅读的难易程度 - 健壮性
是否包含所有异常情况的处理 - 时间效率高和储存量低
算法消耗的时间与内存空间
时间复杂度
算法的时间复杂度是一个函数，定性描述了该算法的运行时间
算法时间构成
1.算法输入的时间
2.编译可执行代码
3.执行指令
4.执行重复的指令 大O表示法计算时间复杂度
- 用常数1取代运行时间中所有的常数 10 ->O(1)
- 在修改运行次数函数中，只保留最高阶项 n^3+2n^2 -> O(n^3)
- 如果最高阶存在且不等于1，则去除相乘的常数 2n^3 -> O(n^3)
- 常数阶
/* 1. 常数阶时间复杂度计算 O(1) *///1+1+1 = 3
大O规则第一条：常数1取代运行时间中的所有常数，即O(1） */
//1+1+1 = 3 O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum);//执行1次
}- 线性阶
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
int i,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}- 对数阶
/*2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}- 平方阶
//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)void testSum5(int n){
int i,j,x=0,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
for (j = 1; j <= n; j++) { //执行n(n+1)
x++; //执行n*n次
sum = sum + x; //执行n*n次
}
} printf("testSum5:%d\n",sum);
}- 立方阶
/*5.立方阶*/ O(n^3)
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}- 指数阶 (不做事例)
各时间复杂度的比较
空间复杂度
空间复杂度通过计算算法所需的存储空间实现，空间计算因素有
- 寄存本身的指令
- 常数
- 变量
- 输入
- 对数据操作的辅助空间
在考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间
计算公式：S(n) = n(f(n)) // n为问题的规模 f(n)为语句关于n所占存储空间的函数int temp; //temp为辅助空间且为常数1 则空间复杂度为O（1）
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}算法衡量
- 最优时间复杂度：完成工作最少花费时间，反映出最理想状态下结果，一般不以它参考
- 最差时间复杂度：完成工作最多花费时间，即最糟糕的情况下算法得出结果，但是它表明算法在此种情况下一定能完成，最有参考价值
- 平均时间复杂度：完成工作平均花费时间，也称加权平均时间复杂度或者期望时间复杂度，当最差时间复杂度相同时，可以用平均时间复杂度对比两个方法
呼应主题，测评算法是否好坏？ 1.算法结果的正确性 2.算法的可阅读性，添加必要的注解，方法名等 3.算法的健壮性，对算法的输入进行容错判断，对边界值小心处理以免越界 4.时间复杂度空间复杂度的计算对比
