乐趣区

关于程序员:初识算法之美

本篇是学习了《趣学算法(第 2 版)》第一章之后总结的。

对算法的了解:

计算机尽管能够高效的进行运算,然而有很多问题拼的不是算力,而是策略。如果没有策略的去计算,那再强的运算能力也只能称为“蛮力”。策略就是帮忙咱们如何用更少的计算步骤、更快的速度去运算出后果。换言之,策略就是你设计算法的思路,目标只有一个就是:快人一步。

计算机不同于人脑,人脑面对问题能够先去“察看”、“剖析”,而后把简单转化成简略问题(跟 数学 题一样,算法就是简便的解题思路)。目前在绝大多数畛域计算机还不具备这个性能,来到了人脑,计算机还只是一个人的应用工具罢了。

算法有两个衡量标准:

  • 工夫长短(工夫复杂度)
  • 占用内存大小(空间复杂度)

先瞻望一下学习历程:

算法学习是一个循序渐进的过程,常常训练解题能力,逐渐积攒解题办法策略,最初内化成本人的常识,灵活运用去应答新的问题。

“初极狭,才通人。复行数十步,恍然大悟。”,挺喜爱这句话😁

算法知识点

  1. 高斯算法(倒序相加)
  2. 数列求和

算法题目

求:$S_n = 1 + 2 + 2^2 + 2^3 + … + 2^{63}=$

该函数属于 爆炸增量函数

做题思路

办法一

公式法

如果还记得高中数学常识,不难发现,这是一个等比数列求和问题,$a_1 = 1,公比 q = 2,n = 64$

等比数列求和公式:$$S_n = a_1 * \frac{1 – q^n}{1 – q},(q ≠ 1)$$

本文暂不解说公式推导过程

代入公式,下面的式子 = $1 * \frac{1 – 2^{64}}{1 – 2} = 2^{64} – 1 = 18446744073709551615$,从而转化问题,解题

办法二

遗记办法叫什么名字了,次要原理就是 销项,使问题转化成第一项和最初一项的差。

依据原式,等号两边同时乘以 2,得式子②$2S_n = 2 + 2^2 + 2^3 + … + 2^{63} + 2^{64}$

用式子② – 原式 = $S_n = 2^{64} – 1 =18446744073709551615$

据专家统计,每颗麦粒的均匀分量约 41.9 毫克,这些麦粒的总重量为:

$18446744073709551615×41.9$

$=772918576688430212668.5(毫克)$

$≈7729000(亿千克)$

全世界人口按 77 亿计算,每人差不多能够分得 100000 千克(即 100 吨)!

总结

常见的算法工夫复杂度有以下几类。

  1. 常数阶。
    常数阶算法的运行次数是一个常数,如 5、20、100。常数阶算法的工夫复杂度通常用 O(1) 示意。
  2. 多项式阶。
    很多算法的工夫复杂度是多项式,通常用 0(n)、$O(n^2)$、$0(n^3)$ 等示意。
  3. 指数阶。
    指数阶算法的运行效率极差,程序员往往像躲“恶魔”一样避开这种算法。指数阶算法的工夫复杂度通常用 $O(2^n)$、$O(n!)$、$O(n^n)$ 等示意。
  4. 对数阶。
    对数阶算法的运行效率较高,通常用 $O(logn)$、$O(nlogn)$ 等示意。
    指数阶增量随着的减少而急剧减少,而对数阶增长迟缓。它们之间的关系如下:

$$O(1)

在设计算法时,咱们要留神算法复杂度增量的问题,尽量避免爆炸级增量。

通过下面一个算法小例子,又勾起了我对数学的趣味。算法跟数学是非亲非故的,平时也要温习一下数学知识,置信也会有所帮忙的。


我是 甜点 cc

酷爱前端,也喜爱专研各种跟本职工作关系不大的技术,技术、产品趣味宽泛且浓重,期待着一个守业机会。本号次要致力于分享集体经验总结,心愿能够给一小部分人一些渺小帮忙。

心愿能和大家一起致力营造一个良好的学习气氛,为了集体和家庭、为了我国的互联网物联网技术、数字化转型、数字经济倒退做一点点奉献。数风流人物还看中国、看今朝、看你我。

本文由 mdnice 多平台公布

退出移动版