算法基本知识，入门必备

目录

1.什么是算法

2.算法的意义

3.如何选择算法

4.时间复杂度

1.什么是时间复杂度

2.时间复杂度的计算方法

3.常见的时间复杂度

5.常见的时间复杂度示例

1、O(1)

2、O(n2)

3、O(n)   

4、Ο(n3)

5、常用的算法的时间复杂度和空间复杂度

6.排序实例

1、冒泡排序

原理分析：

代码实现：

2、选择排序

代码实现：

选择排序代码优化：

3、插入排序

代码实现：

4、快速排序

排序示例：

代码实现：

---

---

算法(algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

mark：我们可以把所有的算法想象为一本“菜谱”，特定的算法比如菜谱中的的一道“老醋花生米”的制作流程，只要按照菜谱的要求制作老醋花生米，那么谁都可以做出一道好吃的老醋花生米。so，这个做菜的步骤就可以理解为：“解决问题的步骤”

假设计算机无限快，并且计算机存储容器是免费的，我们还需要各种乱七八糟的算法吗？如果计算机无限快，那么对于某一个问题来说，任何一个都可以解决他的正确方法都可以的！

当然，计算机可以做到很快，但是不能做到无限快，存储也可以很便宜但是不能做到免费。

那么问题就来了效率：解决同一个问题的各种不同算法的效率常常相差非常大，这种效率上的差距的影响往往比硬件和软件方面的差距还要大。

第一首先要保证算法的正确性

一个算法对其每一个输入的实例，都能输出正确的结果并停止，则称它是正确的，我们说一个正确的算法解决了给定的计算问题。不正确的算法对于某些输入来说，可能根本不会停止，或者停止时给出的不是预期的结果。然而，与人们对不正确算法的看法想反，如果这些算法的错误率可以得到控制的话，它们有时候也是有用的。但是一般而言，我们还是仅关注正确的算法！

第二分析算法的时间复杂度

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的好坏。

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试因为该方法有两个缺陷：

• 想要对设计的算法的运行性能进行测评，必须先依据算法编写相应的程序并实际运行。
• 所得时间的统计计算依赖于计算机的硬件、软件等环境因素，有时候容易掩盖算法的本身优势。

所以只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。

一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此，算法的时间复杂度记做：T(n)=O(f(n))。随着模块n的增大，算法执行的时间的增长率和f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低,算法的效率越高。 

 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级(它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n!)，找出后，f(n)=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T(n)=O(f(n))。

常见的算法时间复杂度由小到大依次为：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

 求解算法的时间复杂度的具体步骤：

• 找出算法中的基本语句，算法中执行最多的那条语句是基本语句，通常是最内层循环的循环体。
• 计算基本语句的执行次数的量级，保证最高次幂正确即可查看他的增长率。
• 用大O几号表示算法的时间性能

 如果算法中包含镶套的循环，则基本语句通常是最内层的循环体，如果算法中包并列的循环，则将并列的循环时间复杂度相加，例如：

 

 

第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。

其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间,而Ο(2n)和Ο(n!)称为指数时间，计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。在选择算法的时候，优先选择前者！

OK我懂对于没有算法基础的同学，看起算法来也很头疼，但是这个是基础和重点，不会算法的开发不是一个合格的开发并且包括语言记得基础也是需要好好整理的！加油吧~~  咱们在一起看下时间复杂度的详细说明吧

这个算法的运行次数函数是f(n)=3。根据我们推导大O阶的方法，第一步就是把常数项3改为1。在保留最高阶项时发现，它根本没有最高阶项，所以这个算法的时间复杂度为O(1)。

并且：如果算法的执行时间不随着问题规模n的增长而增加，及时算法中有上千条语句，其执行的时间也不过是一个较大的常数。此类算法的时间复杂度记作O(1)

解：T(n)=2n2+n+1=O(n2)

一般情况下，对进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。  

 

 

解：T(n)=2+n+3(n-1)=4n-1=O(n)

简单点来去最大值是：Ο(n3)

 

 

 

 

 

 

 

 

 

 

6.排序实例

排序算法是在更复杂的算法中的是一个构建基础，所以先看下常用的排序。

需求：

请按照从小到大对列表，进行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：相邻两个值进行比较，将较大的值放在右侧，依次比较！

原理图：

原理分析：

列表中有5个元素两两进行比较，如果左边的值比右边的值大,就用中间值进行循环替换！
既然这样，我们还可以用一个循环把上面的循环进行在次循环，用表达式构造出内部循环！

代码实现：

 

时间复杂度说明看下他的代码复杂度会随着N的增大而成指数型增长，并且根据判断他时间复杂度为Ο(n2)

需求：

请按照从小到大对列表，进行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：

第一次，从列表最左边开始元素为array[0]，往右循环，从右边元素中找到小于array[0]的元素进行交换，直到右边循环完之后。

第二次，左边第一个元素现在是最小的了，就从array[1],和剩下的array[1:-1]内进行对比，依次进行对比！

对比：

他和冒泡排序的区别就是，冒泡排序是相邻的两两做对比，但是选择排序是左侧的“对比元素”和右侧的列表内值做对比！

原理图：

代码实现：

选择排序代码优化：

 

需求：

请按照从小到大对列表，进行排序==》：[69, 471, 106, 66, 149, 983, 160, 57, 792, 489, 764, 589, 909, 535, 972, 188, 866, 56, 243, 619] 

思路：

一个列表默认分为左侧为排序好的，我们拿第一个元素举例，他左边的全是排序好的，他右侧是没有排序好的，如果右侧的元素小于左侧排序好的列表的元素就把他插入到合适的位置

原理图：

代码实现：

 

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动.他的时间复杂度是：O(nlogn) ~Ο(n2)

排序示例：

假设用户输入了如下数组：

创建变量i=0（指向第一个数据）[i所在位置红色小旗子], j=5(指向最后一个数据)[j所在位置蓝色小旗子], k=6(赋值为第一个数据的值)。

我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：

i=0 j=3 k=6

接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：

 i=2 j=3 k=6

称上面两次比较为一个循环。

接着，再递减变量j，不断重复进行上面的循环比较。

在本例中，我们进行一次循环，就发现i和j“碰头”了：他们都指向了下标2。于是，第一遍比较结束。得到结果如下，凡是k(=6)左边的数都比它小，凡是k右边的数都比它大：

如果i和j没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。

然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。

注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。

代码实现：