【趣学算法】Day1-为什么要学算法？

Love The Way You Lie 2023-09-26 11:22 37阅读 0赞

[14天阅读挑战赛][14]  
*努力是为了不平庸~  
算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！*

![bdf49eded1ba42268abae1d66132de56.png][]

**目录**

一、什么是算法？

二、算法的特征

有穷性

确切性

输入项

输出项

可行性

三、为什么大家都在学算法？

四、学习算法的入门之路

五、算法中时间和空间复杂度

时间复杂度

空间复杂度

六、结语

--------------------

> ### 一、什么是算法？ ###

数据结构+算法＝程序。

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰[指令][Link 1]，算法代表着用系统的方法描述解决问题的策略机制。

直白点儿***算法就是对特定问题求解步骤的一种描叙***。

一个算法的优劣可以用[空间复杂度][Link 2]与[时间复杂度][Link 3]来衡量。

> ### 二、算法的特征 ###

一个算法应该具有以下五个重要的特征：

#### 有穷性 ####

（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止；

#### 确切性 ####

(Definiteness)

算法的每一步骤必须有确切的定义；

#### 输入项 ####

(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；

#### 输出项 ####

(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

#### 可行性 ####

(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算[步骤][Link 4]都可以在有限时间内完成（也称之为有效性）。

> ### 三、为什么大家都在学算法？ ###

![ea30d8a32805486fba1cfda4b64e04f3.png][]

数据结构与算法是我们 IT 从业人员的基础内功，如果算法学的好，那证明你有极强的学习能力和成熟稳定的心智。所以，我们学习算法的核心就是为了提升我们的核心竞争力，最后助你拿到大厂高薪Offer。

学习算法的好处：

1.  思维清晰。
2.  学习力强。
3.  视野开阔。
4.  心智成熟。

> ### 四、学习算法的入门之路 ###

很多时候我们对算法的印象都是感觉非常难的。比如：学不会，不知道从何下手，很枯燥。

但是凡事都得从基础开始，我们总要先去摆正自己的心态，勇于去面对它。

1.  会数据结构的基本操作和经典算法。
2.  会利用数据结构与算法，解决实际问题。
3.  熟练使用和改进数据结构，优化算法。

--------------------

*  至少会一种编程语言（编程语言是我们的载体和工具）
 *  熟悉数据结构
 *  学习常见的几种算法
 *  刷题

刷题网站：

打比赛：Vjudge、POJ、HDU、Code Forces、洛谷

找工作：LeetCode

在线测试系统：OJ(Online Judge) https://vjudge.net/

提交的结果类型：

![be8687ac4bba4e3fb9b52c934166d197.png][]

*  记录坑点（多总结出错的点儿，做记录）

### 五、算法中时间和空间复杂度 ###

> #### 时间复杂度 ####

时间复杂度：算法运行需要消耗的时间。

由于相同配置的计算机进行一次基本运算的时间是一定的，因此，我们将算法基本运算的执行次数作为时间复杂度的衡量标准。

算法的渐进时间复杂度：***`T(n) = O(f(n))`***

***`注：`***其中 f(n) 表示每行代码执行次数之和，而 O 表示正比例关系。

常见的时间复杂度量级：

*  常数阶O(1)

int i = 1;
    int j = 2;
    ++i;
    j++;
    int m = i + j;

上述代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度。

*  对数阶O(logN)

int i = 1;
    while(i<n)
    {
        i = i * 2;
    }

while 循环里，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环 x 次之后，i 就大于 n 了，此时循环退出，也就是说 2 的 x 次方等于 n，那么 x = log2^n。也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)。

*  线性阶O(n)

for(i=1; i<=n; ++i)
    {
       j = i;
       j++;
    }

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

*  线性对数阶O(nlogN)
 *  平方阶O(n²)
 *  立方阶O(n³)
 *  K次方阶O(n^k)
 *  指数阶(2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

> #### 空间复杂度 ####

空间复杂度：算法占用的空间。

空间复杂度是指算法在运行过程中占用了多少存储空间，包含：

（1）输入/输出数据；

（2） 算法本身；

（3）额外需要的辅助空间；

在这里，第一项是必需占用的空间，第二项精简算法的量可以忽略不计，第三项才是我们衡量算法空间复杂度的关键因素。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

算法的渐进空间复杂度：***`S(n)=O(f(n))`***

空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

### 六、结语 ###

知识在于积累，学习需要耐力。没有人能够一蹴而就，付出总会有所回报。

我们学习算法，开始不必纠结于如何去实现算法，而是要先领会算法，能够写伪代码，在我们的大脑中进行程序调试。

[14]: https://marketing.csdn.net/p/bb9f9e25975dba9f9b87f5272afded16
[bdf49eded1ba42268abae1d66132de56.png]: https://img-blog.csdnimg.cn/bdf49eded1ba42268abae1d66132de56.png
[Link 1]: https://baike.baidu.com/item/%E6%8C%87%E4%BB%A4/3225201?fromModule=lemma_inlink
[Link 2]: https://baike.baidu.com/item/%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/9664257?fromModule=lemma_inlink
[Link 3]: https://baike.baidu.com/item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/1894057?fromModule=lemma_inlink
[Link 4]: https://baike.baidu.com/item/%E6%AD%A5%E9%AA%A4/7066340?fromModule=lemma_inlink
[ea30d8a32805486fba1cfda4b64e04f3.png]: https://img-blog.csdnimg.cn/ea30d8a32805486fba1cfda4b64e04f3.png
[be8687ac4bba4e3fb9b52c934166d197.png]: https://img-blog.csdnimg.cn/be8687ac4bba4e3fb9b52c934166d197.png