Skip to content

Latest commit

 

History

History
265 lines (181 loc) · 10.5 KB

20220511-algo-intro.md

File metadata and controls

265 lines (181 loc) · 10.5 KB
isOriginal category tag date
true
数据结构与算法
算法
2022-05-11

算法简介

什么是算法

什么是算法？简单来讲，算法就是用于描述解决问题的方法。而现今普遍对算法的定义为：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令含有一个或多个操作。

算法的特性

算法具有五个基本特性，分别是：

  • 输入
  • 输出
  • 有穷性
  • 确定性
  • 可行性
  1. 输入 & 输出

一个算法，必不可少的是输入输出。算法具有零个或者多个输入，但是至少得有一个或者以上的输出。也就是说，算法可以没有输入，但一定得有输出，输出可以是打印输出，也可以是返回一个或多个值。

  1. 有穷性

所谓有穷性，就是指一个算法在执行一定的步骤之后将自动结束，而不会出现无限循环的情况，而且每个步骤需要在有限的时间内完成。

  1. 确定性

确定性指的是算法的每个步骤都要有具体的含义，不能有歧义。打个简单的比方来说，就像一个人只能沿着一条道走到底，而不能出现遇见分叉路口的情况。

也就是说，在一定条件下，算法只能有一条执行路径，同样的输入只能有唯一的输出结果。

  1. 可行性

指算法的每一步都必须是可行的，也就是说每一步都可以通过执行一定的次数来完成。

算法的设计要求

同一个问题，我们可以通过不同的算法来解决。俗话说得好，条条大路通罗马。同一个目的地，我们可以通过不同的方式到达。

话虽然这么说，但是在设计算法时也得遵循一定的要求。

  1. 正确性

一个算法，必须得保证它能达到最终目的，不然还谈什么。算法的正确性，指的是算法至少应该具有输入、输出和加工处理无歧义性，能够得到问题的正确答案。

算法的正确性也有不同程度的差别，由浅入深大致可以分为以下层次：

  • 算法程序无语法错误。
  • 算法程序对于合法的输入能得到满足要求的输出。
  • 算法程序对于非法的输入能得到满足规格说明的输出。
  • 算法程序对于的特殊的测试数据也有满足要求的输出。
  1. 可读性

可读性是指算法设计出来应该便于阅读、理解和交流。高可读性能够帮助我们更好地理解算法，更加方便我们调试和修改。

  1. 健壮性

一个算法不仅需要对输入的合理情况做出正确的处理，而且对于不合理的情况，也能做出相应的介绍。所谓健壮性，指的就是当算法中输入数据不合法时，它也能做出相关处理，而不会产生异常或者莫名其妙的结果。

  1. 高时间效率

对于同一个问题，虽然有不同解决的算法，但是算法也有好有坏。时间效率指的是算法的执行时间，执行时间越长，效率也低，执行时间越短，效率越高。

  1. 低存储量

除开时间效率之外，存储量也是一个重要的指标。存储量指的是算法在执行过程中所需的最大存储空间，主要指算法程序运行时所占用的内存或外部存储空间。针对同一问题，算法所需空间越少，则算法效果越好，所需空间越多，则算法效果越差。

算法效率衡量方法

前边讲了算法的特性以及算法的设计要求，但都没有明确的方式来衡量一个算法的好坏。为了衡量一个算法的好坏，又提出了时间复杂度和空间复杂度的概念。

时间复杂度

定义

若存在函数 $f(n)$，使得当 $n$ 趋向无穷大时，$T(n) / f(n)$ 的极限值为不等于 0 的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数，记作 $T(n)=O(f(n))$，称 $O(f(n))$ 为算法的 渐进时间复杂度，简称 时间复杂度，用大 O 来表示，称为 大 O 表示法；

推导时间复杂度的原则

  1. 若运行时间是常数量级，则用常数 1 表示；
  2. 只保留时间函数中最高阶项，如 $O(n^2 + 4n)$，保留最高阶项后，成为 $O(n^2)$；
  3. 若最高阶项存在，则省去最高阶项前的系数，如 $O(4n^2)$，省去最高阶项的系数后，成为 $O(n^2)$；

分析时间复杂度的方法

总结起来，对于如何分析一段代码的时间复杂度，主要有如下 3 个实用方法：

  1. 只关注循环执行次数最多的一行代码；
  2. 加法原则：总复杂度等于量度最大的那段代码的复杂度；
  3. 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积；

常见的时间复杂度曲线

常见时间复杂度

$O(1)$

即无论执行多少行，都不会影响到其他区域，此时代码的复杂度就是 $O(1)$，如下面的代码中，假设执行每行代码时间都相同切为 $t$，则 2,3 行各需 1 个执行时间，即为 $t + t = 2t$。此时执行时间复杂度为常数。

void sayHello(String name){
    System.out.prinln("Hello, " + String);
    System.out.prinln("欢迎关注我的公众号：【村雨遥】");
}
$O(log n)$

如下列二分查找代码中，通过 while 循环，能够成倍的缩减搜索范围，假设需要 x 次才能跳出循环，则有 num * 2 * 2 * ... = n ，其中 num 是常数，有 n 个 2 相乘，则有 $num * 2 ^x = n$，从而推出 $x = log_2(n/num)$ ，因此时间复杂度用大 O 表示法表示为 $O(log n)$。

int binarySearch(int[] arr, int target){
    int left = 0;
    int right = arr.length - 1;
    while(left <= right){
        int middle = left + (left - right) / 2;
        if(arr[middle] == target){
            return middle;
        }else if(arr[middle] > target){
            right = middle - 1;
        }else {
            left = middle + 1;
        }
    }

    return -1;
}
$O(n)$

如下面这段代码中，for 循环中的代码被执行了 arr.length 次，因此所需要的时间和数组长度成正比的，因此可以用 $O(n)$ 来表示它的时间复杂度。利用上述推到原则和分析的方法，可以知道下面代码中循环次数最多的是 4,5 行，总的执行时间是 $O(2n)$，抛去系数后，得到最终时间复杂度 $O(n)$。

int sum(int[] arr){
    int total = 0;

    for(int i = 0; i < arr.length; i++){
        total += arr[i];
    }

    return total;
}
$O(n log n)$

如果我们将一个复杂度为 $O(logn)$ 的代码重复执行 $n$ 次，那么此时代码的复杂度不就变成 $O(nlogn)$ 了吗。

void hello (int n){
    for( int i = 1 ; i < n ; i++){
        int m = 1;
        while( m < n ){
            m *= 2;
        }
    }
}
$O(n^2)$

假设我们将时间复杂度为 $O(n)$ 的代码重复执行 $n$ 次，那么此时的时间复杂度就是 $n*O(n)$，即可表示为 $O(n^2)$，表现出来就是双重循环的形式。

void selectionSort(int[] arr, int n){
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[min]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}
$O(n^3)$

和 $O(n^2)$，类似，将时间复杂度为 $O(n^2)$ 的代码嵌套循环一次，此时复杂度就变成了 $O(n^3)$，表现出来就是三重循环嵌套的形式。

void demo(int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                System.out.print("Hello, World");
            }
            System.out.print("------");
        }
        System.out.print("******");
    }
}
$O(n!)$

虽然理论上存在时间复杂度为 $O(n!)$ 的算法，但实践中基本遇不到，所以这里就不展开了。

空间复杂度

定义

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度（即除开原始序列大小的内存，在算法过程中用到的额外的存储空间），反映的对内存占用的趋势，而不是具体内存，也叫作 渐进空间复杂度 ，表示算法的存储空间与数据规模间的增长关系，用 $S(n)$ 来代替；

常用空间复杂度

$O(1)$

算法执行所需临时空间不随某一变量 n 的大小而变化，则该算法空间复杂度为一个常量，表示为 $S(n) = O(1)$；

int num1 = 1;
int num2 = 2;
int total = num1 + num2;
$O(n)$

数组占用内存大小为 n，而且后续未分配新的空间，因此该算法空间复杂度为 $S(n) = O(n)$；

int[] arr = new int[n];
$O(n^2)$

二维数组的情况；

int[][] arr = new int[n][n];

常见排序算法的时间复杂度和空间复杂度

对于面试中常见的的排序算法，以下总结给出了其时间复杂度以及空间复杂度，以及算法稳定性。

排序算法 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(n^{1.3})$ $O(n)$ $O(n^2)$ $O(1)$ 不稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(1)$ 不稳定
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(n^2)$ $O(nlog_2n)$ 不稳定
归并排序 $O(nlog_2n)$ $O(nlog_2n)$ $O(nlog_2n)$ $O(n)$ 稳定
计数排序 $O(n+k)$ $O(n+k)$ $O(n+k)$ $O(n+k)$ 稳定
桶排序 $O(n+k)$ $O(n)$ $O(n^2)$ $O(n+k)$ 稳定
基数排序 $O(n*k)$ $O(n*k)$ $O(n*k)$ $O(n+k)$ 稳定

总结

好了，以上就是今天文章的内容了。主要介绍了算法的定义、算法的特性、算法的设计要求以及算法效率的衡量方法。时间复杂度的定义、推导原则以及常见时间复杂度，还对空间复杂度定义以及常见空间复杂度进行了介绍，最后则是总结了常见排序算法的时间复杂度和空间复杂度。