数据结构与算法2-算法

算法是解决问题的一种方法。例如高斯的高斯公式，计算面积的公式等。都是一种算法，用来解决某些问题。

算法特性

• 有穷行: 算法可以在某一个条件下自动结束而不是出现无限循环
• 确定性: 算法执行的每一步骤在一定条件下只有一条执行路径，一个相同的输入对应相同的一个输出
• 可行性: 算法每一步骤都必须可行，能够通过有限的执行次数完成
• 输入: 算法具有零个或多个输入
• 输出: 算法至少有一个或多个输出

算法效率衡量方法

• 正确性
  只有一个能解决问题的正确算法才是我们所需要的。所以设计好一个算法的首要目标就是这个算法能解决问题。
• 可读性
  代码是写给计算机运行的，而读代码是我们程序员来读的，一个算法如果写的晦涩难懂难以理解，这对未来的维护以及拓展将会造成很大的问题。所以并不是代码越少就是越厉害，有易懂的注释与清晰的逻辑才是最美的。
• 健壮性
  一个好的算法需要考虑到各种情况，对各种情况都要进行处理，避免某些情况造成算法的错误计算等。
• 时间效率和存储效率
  这就是我们经常听到的时间复杂度与空间复杂度，花最少的消耗与最少的消耗完成任务。

时间复杂度(大O表示法)

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。

推导大O阶方法

• 用常数1取代运行时间中所有常数 3->1 O(1)
• 在修改运行次数函数中,只保留最高阶项 n³+2n²+5 -> O(n³)
• 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n³ -> n³

常见的算法复杂度

• 常数阶-O(1)

//1常数阶   执行3次。O(1)
void testNum1(int n){
    int sum = 0 ;//执行一次
    sum = (n+1)*n/2; //执行一次
    printf("sum=%d\n",sum);//执行一次
}

• 线性阶-O(n)

//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

• 平方阶-O(n²)

//x=x+1; 执行n*n次 ->O(n²)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

• 对数阶-O(logn)

/* 2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){
    int count = 1;         //执行1次
    //n = 10
    while (count < n) {
        count = count * 2;
    }
}

• 立方阶-O(n³)

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次
            }
        }
    }
}

• nlogn阶-O(nlogn)

void testA(int n){
    int count = 1;         //执行1次
    //n = 10
for (int i = 0; i< n; i++) {
        while (count < n) {
        count = count * 2;
        }
    }
}

• 指数阶（不考虑）

image.png

      0(1) < 0(logn) < 0(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn) 

最坏情况与平均情况

我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置，那么时间复杂度为O(n)。
平均运行时间是期望的运行时间。
最坏运行时间是一种保证。在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

空间复杂度

空间复杂度就是运行某一个算法，需要多少额外的辅助空间来进行这个算法的运行。
算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
如果算法执行时所需要的辅助空间相对于输入数据量是一个常数,则成这个算法原地工作,辅助空间为O(1).

int temp = a;
a = b;
b = temp;

消耗了额外的一个变量，即空间复杂度为O(1)

int a[n] = {0};//n为常数
for(int i = 0; i < n;i++){
    a[i] = array[n-i-1];
}
for(int i = 0; i < n; i++){
    array[i] = a[i];
}

消耗了额外的n个空间的数组，即空间复杂度为O(n)

常用算法

排序法	最差时间分析	平均时间复杂度	稳定度	空间复杂度
冒泡排序	O(n2)	O(n2)	稳定	O(1)
快速排序	O(n2)	O(n*log2n)	不稳定	O(log2n)~O(n)
选择排序	O(n2)	O(n2)	稳定	O(1)
二叉树排序	O(n2)	O(n*log2n)	不一顶	O(n)
插入排序	O(n2)	O(n2)	稳定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	不稳定	O(1)
希尔排序	O	O	不稳定	O(1)