算法基本知识及其时间复杂度的计算

迷南。 2022-03-21 13:28 184阅读 0赞

（一）什么是算法？算法是解决特定问题的求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作。  
（二）算法的特性：（1）***输入输出*** ：算法具有多个或零个输入，比如像“hello world”，这个代码不需要任何输入，此类代码不需要任何输入，因此**算法可以是零输入的**，但是**算法至少应该有一个或多个输出**；试想，一个算法如果不需要输出 ，那你用这个算法来干嘛。（2）***有穷性***：是指算法在执行完有限的步骤之后会自动结束而不是陷入无限循环，并且每一个步骤在*可接受*的时间内完成（你总不能一个算法让计算机运行好几十年才能运行出结果吧）。（3）***确定性***：算法的每一步骤都具有确定含义，不会出现二义性。即在相同的输入下对于确定的算法来讲只会有唯一的输出结果。（4）***可行性***：算法的每一步都必须是可行的，也就是说，每一步都可以通过执行有限的次数完成。  
（三）算法设计的要求：（1）***正确性***：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。但是算法的“正确”通常在用法上有很大的差别，大致分为以下几个层次。\*1.算法没有语句错误。2.算法程序对于合法的输入数据能够产生满足要求的输出结果。3.算法程序对于非法的输入数据能够得到满足规格说明的结果。4.算法程序对于精心选择的、甚至刁难的测试数据都有满足要求的输出结果。\*这四层含义对算法的要求也是从低到高排列，层次四最为困难，以至于我们几乎不可能逐一验证所有的输入都得到正确的输出结果。在一般情况下，我们把前三条作为一个算法是否正确的标准。（2）***可读性***：算法设计的另一目的就是为了方便阅读、理解和交流。你用很简单的代码实现了一个很复杂的功能，并且没有注释什么的，时间一久，可能自己都不知道当初到底写了些什么，因此可读性是衡量算法好坏的一个重要标志。（3）***健壮性***：当用户的输入数据不合理时，算法能给出相应的处理方案，而不是产生异常或者出现莫名其妙的结果。（4）***时间效率高而储存量低***：简单的讲就是花最少的材料办最大的事。  
（四）算法的时间复杂度：用大写的O()来体现算法时间复杂度的记法，我们称之为大O记法。常见的推导大O阶的方法：  
**1.用常数1取代运行时间中的所有加法常数。  
2.在修改后的运行次数函数中，只保留最高阶项。  
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。**  
得到的结果就是大O阶。常见的大O阶分析：  
1.*常数阶*。考虑如下代码  
![在这里插入图片描述][20190201225453833.png]  
这个算法的运行函数为f(n) = 4；按照我们上面的办法，将常数4改为1，在保留最高阶项时发现他没有最高阶项，因此时间复杂度为O(1)。那如果是这样呢？![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]  
大家不用去数这一共执行了多少次，**因为算法时间复杂度与问题的大小无关（即与n的大小无关），不管这个常数是多少，我们都记作O(1)，而不能是O(4)，O（14）等其他任何数字。执行时间恒定的算法我们称之为具有O（1）的时间复杂度，又叫常数阶。  
2.*线性阶*：考虑如下代码：  
![在这里插入图片描述][20190201230432784.png]  
该循环的时间复杂度为O（n），因为循环体中的代码必须执行n次。  
3.*对数阶*：考虑如下代码：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]  
每次循环以后，count都会乘以2，因此循环会在（假设）x个2相乘大于n的时候退出。因此可以得到2^x = n，即x = log2(n)，所以这个循环的时间复杂度为O（logn）。  
4.*平方阶*：两个都会循环n次的嵌套，时间复杂度自然就是O（n^2）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]  
如果是下面这种情况呢？![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]  
此时我们可以推导，外层循环执行第一次的时候内层循环执行n次，外层循环执行第二次的时候内层循环执行了n - 1次，外层循环第三次的时候内层循环执行n - 2次，以此类推我们可以得到总的执行次数为n + (n - 1) + (n - 2) +…+ 1 = n(n + 1) / 2=n^2 / 2 + n / 2。按照上述方法，第一步，没有 加法常数，因此不考虑；第二步，只保留最高阶项，变成了n^2/2;第三步：去除这个项相乘的常数，也就是去除1 / 2，最终这个代码的时间复杂度为O（n^2）。经过以上实例我们可以看出，大O阶的推导并不难，难的是你对数列以及一些数学基本知识的应用以及掌握情况，也就是说他更多的考察你的数学能力。  
（五）常见的时间复杂度  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]  
常见的时间复杂度的耗费时间的大小依次是O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n!)。**  
最坏情况运行时间：指运行时间不会再坏了，在应用中，这是一项最重要的需求，一般而言，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。

[20190201225453833.png]: /images/20220321/11c2281b672b4a86bfd5b56c51ca9571.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70]: /images/20220321/335261a3df6747c187a5892bb2f91df1.png
[20190201230432784.png]: /images/20220321/40f9f49c3d7c4887843b84b545510931.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 1]: /images/20220321/208ee5f529fb4b3aaa401e955f83c7be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 2]: /images/20220321/9bfe8095bd4c4d74951355568eacfe95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 3]: /images/20220321/81950df0bacf4847a547314194b108f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjE0NTI0_size_16_color_FFFFFF_t_70 4]: /images/20220321/76442e41ed6e430ba49d3621e5b68ee6.png