算法简单理解(一)

前言:
对于算法，本人开始其实蛮揪心的，只是知道它的作用和用法，对于算法没有什么深刻的理解，而且感觉算法，哇，好难的样子。😄 开始看的时候头都是懵的，后来发现，其实自己的切入点不对。现在整理下思路，希望也能帮助到你对算法的认识。

很多人可能跟我起初是一样的，学习了算法，而不知道什么时候合理的去选择使用一种算法。

所以，就以 Search 需求来理解认识算法.

介词

首先要了解一下算法里面的基本概念

N 代表数据量

大O符号 代表上界 (upper bound) -----代表最多最多会用到多少时间

大Ω符号 代表下界 (lower bound) -----代表最少最少会用到多少时间

大Θ符号 代表上界跟下界刚好相等

• O(N) 在超过一定规模时候，基本上这个算法花费的时间 (或是空间) 会跟数据量 N 成正相关。也就是说如果 N 增加 3 倍，花费的时间/空间也会增加 3 倍。
• 算法上我们通常只在乎 O (读音 Big O)。毕竟 Ω 这种最少需要花费多少时间/空间，并不是我们所关心，而我们需要关系的是 最多最多需要花费的时间 。
• log 表达的相对增长率 。 --- 算法中的 log

常见的 Complexity

Complexity说明

• O(1) 常数，花费时间跟数据量基本上无相关,也可以说在搜索只需要1次。比如hash算法。

• O(lgN) 对数，花费时间跟数据量 N 取 Log2 正相关。比如二元搜索法

• O(N) 花费时间跟数据量 N 成正相关。比如for循环

• O(N lg N) 花费时间跟数据量 N * lg N 成正相关

• (N2) 花费时间跟数据量 N 的平方成正相关

• O(N3) 花费时间跟数据量 N 的三次方成正相关

具体的各种算法的表达式，后面会依次讲解

下面这张图是算法的对比，左边最少依次顺序

Complexity 的威力

• 小数据量 用简单易懂的方法就好

• 大数据量 用好的算法

下表来说，也许 O(lgN)比较难写，小数据量也比较慢。但是数据量超过一定程度之后，威力自然显现出来!

从表中我们可以看到，当数据量为1的时候，O(lgN) 的方法比较慢，但是当数据了越来越大的时候，它的威力越来越大，所以你要不要采用一个算法，完全是要看你的数量而定和你要解决的问题而定。