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

Nino 发布于2019-08-22 11:19 / 1267人阅读

摘要：你需要知道的算法之基础篇前言很多时候我们都会感慨要是当时了多好啊，现在也不至于这样难堪了。但是我们不可能又没必要对每个算法进行测试，只需要知道大概的哪个算法执行所花费的时间多，哪个花费的时间少就行了。

你需要知道的算法之基础篇 0 - 前言

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

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

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

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

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取代运行时间中的所有加法常数

只保留最高阶项

去除最高阶的常数

举好多栗子

常数阶

let sum = 0, n = 10; // 语句执行一次
let sum = (1+n)*n/2; // 语句执行一次
console.log(`The sum is : ${sum}`) //语句执行一次

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

线性阶

let i =0; // 语句执行一次
while (i < n) { // 语句执行n次
  console.log(`Current i is ${i}`); //语句执行n次
  i++; // 语句执行n次
}

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

对数阶

let number = 1; // 语句执行一次
while (number < n) { // 语句执行logn次
  number *= 2; // 语句执行logn次
}

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

平方阶

for (let i = 0; i < n; i++) { // 语句执行n次
  for (let j = 0; j < n; j++) { // 语句执行n^2次
    console.log("I am here!"); // 语句执行n^2
  }
}

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

常见时间复杂度的比较

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

O(1) 3 - 结语

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

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

原文地址：点击此处

GPU云服务器云服务器之基础篇你知道你应该知道学习算法需要什么基础

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/92192.html

我的阿里之路+Java面经考点

摘要：我的是忙碌的一年，从年初备战实习春招，年三十都在死磕源码，三月份经历了阿里五次面试，四月顺利收到实习。因为我心理很清楚，我的目标是阿里。所以在收到阿里之后的那晚，我重新规划了接下来的学习计划，将我的短期目标更新成拿下阿里转正。我的2017是忙碌的一年，从年初备战实习春招，年三十都在死磕JDK源码，三月份经历了阿里五次面试，四月顺利收到实习offer。然后五月怀着忐忑的心情开始了蚂蚁金...

姘搁『 2019-08-15 14:42 评论0 收藏0
自学人工智能之数学篇，数学入门并不难

摘要：写本文的目的，希望结合众家之长，试图解决数学对机器学习入门的困扰。这里假设你上过大学的数学课，你就具备了机器学习的数学入门门槛了，之后的数学啃一啃是可以下来的。写这篇文章很久想了很久，到底该怎么写？关于数学与机器学习的关系，观点很多。写本文的目的，希望结合众家之长，试图解决数学对机器学习入门的困扰。现在数学困扰大家主要有这几个方面： 1、机器学习需要的数学知识是不是很难，网上...

fox_soyoung 2019-06-26 18:32 评论0 收藏0
自学人工智能之数学篇，数学入门并不难

摘要：写本文的目的，希望结合众家之长，试图解决数学对机器学习入门的困扰。这里假设你上过大学的数学课，你就具备了机器学习的数学入门门槛了，之后的数学啃一啃是可以下来的。写这篇文章很久想了很久，到底该怎么写？关于数学与机器学习的关系，观点很多。写本文的目的，希望结合众家之长，试图解决数学对机器学习入门的困扰。现在数学困扰大家主要有这几个方面： 1、机器学习需要的数学知识是不是很难，网上...

txgcwm 2019-07-30 17:17 评论0 收藏0