首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法入门

算法入门

作者头像
硬核编程
发布2019-08-19 21:29:33
3830
发布2019-08-19 21:29:33
举报

转载请联系授权

01

算法的定义

用不同顺序写不同语句也能得到一样结果,不同的是 "算法",意思是:解决问题的具体步骤。即使结果一致,有些算法会更好,一般来说,所需步骤越少越好。不过有时我们也会关心其他因素,比如占多少内存。

"算法" 一词来自 波斯博识者 阿尔·花拉子密(1000 多年前的代数之父之一)如何想出高效算法 - 是早在计算机出现前就有的问题,从而诞生了专门研究计算的领域,然后发展成一门现代学科—计算机科学!

02

排序算法

记载最多的算法之一是"排序",排序到处都,比如给名字、数字排序,找最便宜的机票,按最新时间排邮件,按姓氏排联系人等这些都要排序。你可能想"排序看起来不怎么难… 能有几种算法呢?" ,答案是超多。计算机科学家花了数十年发明各种排序算法,还起了酷酷的名字,比如冒泡排序,快速排序,插入排序,归并排序等。

我们来试试排序!试想有一堆机票价格,都飞往 印第安纳波利斯 (美国地名)。

上图的这样一组数据 叫"数组"(Array),来看看怎么排序(建议拿出笔和纸跟着说明来排序),先从一种简单算法开始,先找到最小数,从最上面的 307 开始,因为现在只看了这一个,所以它是最小数,下一个是 239,比 307 小,所以新的最小数变成 239。下一个是 214 ,新的最小数,250 不是,384, 299, 223, 312 都不是,现在扫完了所有数字,214 是最小的

为了升序排列(从小到大排序),把 214 和最上面的数字,交换位置,刚排序了一个数字。现在重复同样的过程,这次不从最上面开始,从第 2 个数开始,先看到 239,我们当作是 "最小数",扫描剩下的部分,发现 223 最小,所以把它和第 2 位交换,重复这个过程,从第 3 位数字开始,让 239 和 307 互换位置,重复直到最后一个数字。

数字排好了,可以买机票了!

刚刚这种方法,或者说算法,叫 选择排序 - 非常基础的一种算法

以下是"伪代码"

03

算法复杂度

这个函数可以排序8个, 80个或8千万个数字,函数写好了就可以重复使用。这里用循环遍历数组,每个数组位置都跑一遍循环,找最小数然后互换位置,每个数组位置都跑一遍循环,找最小数然后互换位置,可以在代码中看到这一点(一个 for 循环套另一个 for 循环)。这意味着,大致来说,如果要排 N 个东西,要循环 N 次,每次循环中再循环 N 次,共 N*N, 或 N。算法的输入大小和运行步骤之间的关系叫算法的复杂度,表示运行速度的量级。

计算机科学家们把算法复杂度叫大 O 表示法,算法复杂度 O(N*N)效率不高

前面的例子有 8 个元素(n=8), 8*8= 64,如果 8 个变 80 个,运行时间变成 80*80 = 6400。虽然大小只增长了 10 倍(8 到 80),但运行时间增加了 100 倍!(64 到 6400 )。随着数组增大,对效率的影响会越来越大。这对大公司来说是个问题,比如谷歌要对几十亿条信息排序。

作为未来的计算机科学家你可能会问:有没有更高效的排序算法?我们下节继续

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2019-06-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员成长充电站 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 01
  • 算法的定义
  • 02
  • 排序算法
  • 03
  • 算法复杂度
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档