算法的了解

算法究竟是什么, 都包括些什么

su 收录于数据结构

2017-01-01 约 2162 字预计阅读 5 分钟次阅读

算法定义

算法是解决特定问题求解步骤的描述, 在计算机中表现为指令的有限序列, 并且每条指令表示一个或多个操作.

算法是针对一种或者是一类问题的解决方案.

算法的特性

算法具有5个基本特性: 输入, 输出, 有穷性, 确定性和可行性.

输入输出

算法具有0或者多个输入. 对于个别场景, 比如打印输出字符串. 可能会不需要任何的输入参数.

算法至少1个或者多个输出. 算法一定要有输出, 否则算法也就没有计算的意义. 输出的形式可以是打印输出或者是返回1个以上的值

有穷性

就是算法应该可以有限时间内可以执行完毕.

有限时间: 一个算法如果计算需要几天,几月那就有点扯蛋了. 基本这不是我们需要的算法.
执行完毕: 可以正常的执行结束. 而不会出现死循环的问题.

确定性

算法的每一步骤都具有确定的含义, 不会出现二义性.

比如说. 某种条件下只会有一条执行的代码线路. 而不会因为随机性而导致相同的输入结果而出现了不同的输出结果.

可行性

算法的每一步必须是可行的. 也就是说, 每一步都能够通过执行有限的次数来完成.

算法的设计

正确性: 算法至少可以保证结果的准确性.
可读性: 算法的另一个目的是为了便于阅读, 理解和交流. 为了日后不是非常难于调试和修改要尽可能让代码可以逻辑清晰. 不要写出只能自己和机器才能看懂的代码.
健壮性: 能对一些非法的输入进行容错的处理. 边界问题的处理.
时间效率高和存储量低: 这是算法不断演进的根本因素.

算法效率的度量方法

事后统计法

这是方法的前置条件是. 算法已经存在. 通过设计好的程序和数据, 利用计算机计时器对不同算法编制的程序的运行时间进行比较. 通过执行时间来决定算法的好坏.

缺陷:

需要设计出算法, 但不一定这个算法就有用, 可能花费时间写出的算法只因测试一遍就放弃代码.
时间的消耗依赖计算机的硬件, 和软件等因素.
测试数据一般都是一点盖面的测试.

一般是不使用此统计法

事前分析估算

比如: 一个高级语言编写的程序的运算时间取决于如下因素:

算法采用的策略, 方法
编译产生的代码质量
问题的输入规模
机器执行指令的速度

其中2和4分别是由软件和硬件来决定的. 所以剩下的两种就是关键因素. 可以认为代码需要进行计算的次数. 如下:两个代码片段.

场景: 对1~100进行所有数累加求和.

private int normal_calculate(int count){
    int sum = 0;                  // 执行 1 次
    
    for(int i=0; i<count ; i++){  // 执行 count+1
        sum += i;                 // 执行 count
    }
    
    return sum;                   // 执行 1 次
}

private int optimize_calculate(int count){
    int sum = 0;                   // 执行 1 次
    
    sum = ( 1 + count ) * count/2; // 执行 1 次
    
    return sum;                    // 执行 1 次
}

可以看出第一种是每个数进行累加的语句执行次数总共是2 * count + 3次

而第二种通过高斯定律只需要执行3次即可.

时间复杂度

通常比较两个算法的好坏是通过对比时间复杂度来区分. 通常用大写O()来体现算法时间复杂度的记法. 称之为大O记法

例如最常见的O(1)常数阶, O(n)线性阶, O(n^2)平方阶

推导大O阶的方法

推导规律:

用常数1来取代运行时间中的所有加法常数
在修改后的运行次函数中, 只保留最高阶项
如果最高阶项存在且不是1, 则去除与这个项相乘的常数

常数阶

例如上面代码块2中的. 运行次数函数是f(count) = 3. 那么根据第一要点. 要把常数3改为1. 在保留最高阶项是发现没有最高阶项. 所以算法的时间复杂度就是O(1)

常数不论是多少, 都记做为O(1). 不要出现其他的数字. 而分支无论真假, 都不会随着n的变大而变大所以其时间复杂度不变.

线性阶

通常情况下循环结构的运行情况是分析时间复杂度的大部分的场景.

例如上面代码块1 中的总执行次数是 f(count) = 2*count + 3

那么根据推导规律其时间复杂度就是O(n)也可以是O(count).

对数阶

例如求一个数能被2整除多少次(不包括0). 那么就相当于求这个数的2^X = n得到x = log2 n 所以时间复杂度就是O(logn)

平方阶

一个n * n乘法表. 的双循环次数是1 + 2 + ... + (n-2) + (n-1) + (n)

= n * (n + 1) / 2 = n^2 / 2 + n/2

根据推导规律第2和3条. 就会变成了O(n^2)的时间复杂度.

常见的事件复杂度

常见的时间复杂度所耗费的时间从小到大依次是:

O(1) < O(log n) < O(n) < O(n*log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

以上的有很多是不太符合实际情况的算法时间的. 因为例如 2^n, n^3, n!. n只要是稍微大一点的数. 最终结果都会多几个量级的增加. 这么费时间的算法, 显示生活中也不会采用的.

情况的采用

在我们对一组无序数字进行排序的时候. 总会出现所谓最好, 最坏, 正常(平均)的场景.

比如恰好这组数字是排序好的一组结果. 此时是最好情况. 一次查看就结束.
比如恰好这组数字每一个数字都需要进行比较直到最后一个数字. 此时就是最坏情况.
剩下的的就是中间范围的结果了. 我们可以认为其是平均值(最好+最坏的一半)

因为最坏情况是一种保证, 那就是运行的时间不会再坏. 所以通常情况下都是以最坏时间当做其运行时间.

算法空间复杂度

有时候不一定需要非要追求极致的时间算法. 巧妙的使用空间换时间的概念. 往往会让事情变得更简单.

例如: 写一个函数, 可以判断传入的参数是否是100以内的质数. 如果通过规律循环比对完成一个算法. 那么每次的数字都是需要计算的.

那么如果. 用一个内部的数组. 这个数组的大小就是0~100. 然后如果对应的下标是质数那么数组就存放1. 否则就是0. 这样每次传入的参数只需要作为数组下标去取值直接判断即可.

当然. 根据具体场景不同. 到底是否使用空间换时间的方法需要商酌. 空间的浪费是否真的有必要. 数据的保存是否很占用空间. 能带来的好处是否高于空间浪费的弊端等…

目录