你需要知道的算法之基础篇

0 - 前言

很多时候我们都会感慨:要是当时×××了多好啊,现在也不至于这样难堪了。

后悔的时候千千万,一觉醒来过眼云烟。

我也和芸芸众生一样在学校的时候没有好好的理解思考一些东西,等到了真正需要用的时候才知道书到用时方恨少。有道是知错能改,那为什么有道 == 知错能改呢?下面请允许我开始真正的内容:

本文通篇都是一些概念,但是你需要知道这些更有利于理解时间复杂度等一些概念是什么、怎么来的、为什么需要这个东西(what、where、why)。

1 - 算法

算法的定义是这样的:解题方案的准确而完善的描述,是一系列解决问题的清晰指令。巴拉巴拉的,虽然是一小句但还是不想看(题外话:有时候吧专业名词记下来面试的时候还是挺有用的),其实就是解决一个问题的完整性描述。只不过这个描述就可能是用不同的方式或者说是“语言”了。

2 - 算法的效率

既然算法是解决问题的描述,那么就像一千个人眼中有一千个阿姆雷特他大姨夫一样,解决同一个问题的办法也是多种多样的,只是在这过程中我们所使用/消耗的时间或者时间以外的代价(计算机消耗的则为内存了)不一样。为了更快、更好、更强的发扬奥利奥..哦不,提高算法的效率。所以很多时候一个优秀的算法就在于它与其他实现同一个问题的算法相比,在时间或空间(内存)或者时间和空间(内存)上都得到明显的降低。

所以呢,算法的效率主要由以下两个复杂度来评估:

  1. 时间复杂度:评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
  2. 空间复杂度:评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时,时间复杂度要比空间复杂度更容易出问题,所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话,复杂度就是指时间复杂度。

2.0 - 时间复杂度

接下来我们还需要知道另一个概念:时间频度。这个时候你可能会说:“不是说好一起学算法吗,这些东东是什么?赠品吗?”。非也非也,这是非卖品。

因为一个算法执行所消耗的时间理论上是不能算出来的,没错正是理论上,so我们任然可以在程序中测试获得。但是我们不可能又没必要对每个算法进行测试,只需要知道大概的哪个算法执行所花费的时间多,哪个花费的时间少就行了。如果一个算法所花费的时间与算法中代码语句执行次数成正比,那么那个算法执行语句越多,它的花费时间也就越多。我们把一个算法中的语句执行次数称为时间频度。通常(ps:很想知道通常是谁)用T(n)表示。

在时间频度T(n)中,n又代表着问题的规模,当n不断变化时,T(n)也会不断地随之变化。为了了解这个变化的规律,时间复杂度这一概念就被引入了。一般情况下算法基础本操作的重复执行次数为问题规模n的某个函数,用也就是时间频度T(n)。如果有某个辅助函数f(n),当趋于无穷大的时候,T(n)/f(n)的极限值是不为零的某个常数,那么f(n)T(n)的同数量级函数,记作T(n)=O(f(n)),被称为算法的渐进时间复杂度,又简称为时间复杂度。

2.1 - 大O表示法

用O(n)来体现算法时间复杂度的记法被称作大O表示法

一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

大O表示法O(f(n))中的f(n)的值可以为1、n、logn、n^2 等,所以我们将O(1)、O(n)、O(logn)、O( n^2 )分别称为常数阶、线性阶、对数阶和平方阶。下面我们来看看推导大O阶的方法:

推导大O阶

推导大O阶有一下三种规则:

  1. 用常数1取代运行时间中的所有加法常数
  2. 只保留最高阶项
  3. 去除最高阶的常数

举好多栗子

  • 常数阶

这样的一段代码它的执行次数为 3 ,然后我们套用规则1,则这个算法的时间复杂度为O(1),也就是常数阶。

  • 线性阶

这个算法中代码总共执行了 3n + 1次,根据规则 2->3,因此该算法的时间复杂度是O(n)。

  • 对数阶

上面的算法中,number每次都放大两倍,我们假设这个循环体执行了m次,那么2^m = nm = logn,所以整段代码执行次数为1 + 2*logn,则f(n) = logn,时间复杂度为O(logn)。

  • 平方阶

上面的嵌套循环中,代码共执行 2*n^2 + n,则f(n) = n^2。所以该算法的时间复杂度为O(n^2 )

常见时间复杂度的比较

常见的时间复杂度函数相信大家在大学中都已经见过了,这里也不多做解释了:

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)

3 - 结语

曾经有一份能够在学校好好学算法的机会,我没有好好珍惜,直到失去的时候我才追悔莫及。

从今天开始,我会好好的把之前很多自己没有去理解的各种基础、底层知识好好的嚼几遍。与诸君共勉!


本文作者:Noonnnne

原文链接:http://www.iamdzt.cn/2017/12/17/%E4%BD%A0%E9%9C%80%E8%A6%81%E7%9F%A5%E9%81%93%E7%9A%84%E7%AE%97%E6%B3%95%E4%B9%8B%E5%9F%BA%E7%A1%80%E7%AF%87/

原文发布于微信公众号 - 腾讯NEXT学位(NextDegree)

原文发表时间:2017-12-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

这是一道算法面试题,不妨看看

要想从start 点到 finish 点,那么,必然经过 h1 或 h2 点,所以,问题转化为:求 start 点到 h1 点,或 start 点到 h2点的路...

944
来自专栏小红豆的数据分析

小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

直接说基础语法,也许大家不会感兴趣。前言之后的这一章,给大家介绍一下我最近写出来的一个小功能。用python语言实现GA算法来解决TSP问题,希望以此来激发大家...

2894
来自专栏深度学习思考者

最短路径(一)——多源最短路径

引出问题:多源最短路径的问题 暑假,小文准备去一些城市旅游。为了节省经费以及方便计划旅程,小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。 我们...

22110
来自专栏灯塔大数据

每周学点大数据 | No.3算法设计与分析理论

No.3期 算法设计与分析理论 在计算机科学中,研究算法的设计和评价算法“好坏”的分支,称为算法设计与分析理论。它研究如何去设计解决问题的算法,同时给出一个对...

30210
来自专栏后端技术探索

算法之经典背包问题分析与实例

我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,...

981
来自专栏机器之心

机器学习时代的哈希算法,将如何更高效地索引数据

2525
来自专栏大数据

大数据图:循环点阵

本文的内容最初由Marko Rodriguez和Bobby Norton在Aurelius博客上共同撰写。

3425
来自专栏C语言及其他语言

【每日一题】问题 1429[蓝桥杯][历届试题]兰顿蚂蚁

题目描述 ? 兰顿蚂蚁,是于1986年,由克里斯·兰顿提出来的,属于细胞自动机的一种。 平面上的正方形格子被填上黑色或白色。在其中一格正方形内有...

2926
来自专栏C语言及其他语言

[每日一题]矩阵转置(1242)

题目描述 输入N*N的矩阵,输出它的转置矩阵。 输入 第一行为整数N。 接着是一个N*N的矩阵。 输出 转置矩阵 样例输入 2 1 2 1 2 样例输出 1 ...

3549
来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

1266

扫码关注云+社区

领取腾讯云代金券