一、算法：
1、解释
算法是解决问题的方法，如何更好地更有效的解决问题，就需要设计一个好的算法，好的算法有以下要求。
2、算法特性
- 有穷性：算法必须在执行有限的次数后结束
- 确定性：算法的每一步必须有确定的含义
- 可行性：算法的每一步必须可执行，每一步都能通过执行有限次数完成
- 输入输出：算法要有输入有输出
3、算法的评价标准
- 正确性：算法要能正确的解决问题并输出正确结果
- 可读性：设计的算法要让人能看明白
- 健壮性：算法要能对不合理的数据输入有反应能力和处理能力
- 高效性：算法需要高效的处理问题，快速得到结果
二、数据结构
算法要存储到内存中执行，这就要有数据结构，以下是几种数据结构
数据结构是计算机存储、组织数据的方式。
1、逻辑结构
逻辑结构
集合结构：数据元素的集合，元素与元素之间没有任何关系
线性结构：一对一
树形结构：一对多
图形结构：多对多
2、物理结构
物理结构
- 顺序存储结构：按顺序存储，存储地址是连续的
- 链式存储结构：有方向性的存储，存储地址不连续，需要同时保存元素的数据和地址，通过地址找到关联的数据
三、时间复杂度和空间复杂度
时间复杂度和空间复杂度是衡量一个算法好坏的重要指标
时间复杂度
时间复杂度计算的是算法执行最差情况下的执行次数，非常数的取最高阶，存在最高阶的则省去最高阶前的系数
- 常数阶，>1的常数都记作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+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum);//执行1次
}
//x=x+1; 执行1次
void add(int x){
x = x+1;
}
- 线性阶，取最高阶并省去最高阶前的系数： O(n)
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+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次
}
- 对数阶 O(log n)
/*执行log 2 n 次 -> O(logn)*/
void test(int n){
for(int i=1; i<n; i*=2){ //执行log 2 n 次
printf("%d\n",i);
}
/*2的x次方等于n x = log 2 n -> O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) { //执行log 2 n 次
count = count * 2;
}
}
- 平方阶 O(n^2)
//x=x+1; 执行n*n次 ->O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
int sum = 0;
for(int i = 0; i < n;i++)
for (int j = i; j < n; j++) {
sum += j;
}
printf("textSum4:%d",sum);
}
//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);
}
- 立方阶 O(n^3)
//1+n+n*n+n*n*n+n*n*n = 1+n+n^2+2*n^3 -> 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次
}
}
}
}
n(log n)阶 O(n(log n))
指数阶 O(2^n)
时间复杂度的比较
O(1) < O(log n) < O(n) < O(n(log n)) < O(n^2) < O(n^3) < O(2^n)
空间复杂度
空间复杂度计算的是执行算法的辅助空间，比如借助一个临时变量交换两个字符的位置，这个临时变量所占空间就是算法的空间复杂度
//两种算法的空间复杂度比较
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1)，只需要一个临时变量
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
//算法实现(2)，数组作临时变量占用更多内存，增加了空间复杂度
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
for(int i = 0;i < 10;i++)
{
printf("%d\n",a[i]);
}
