一、算法：

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]);
        
    }