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

（一）什么是算法？算法是解决特定问题的求解步骤的描述，在计算机中表现为指令的有序序列，并且每条指令表示一个或多个操作。
（二）算法的特性：（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.常数阶。考虑如下代码

这个算法的运行函数为f(n) = 4；按照我们上面的办法，将常数4改为1，在保留最高阶项时发现他没有最高阶项，因此时间复杂度为O(1)。那如果是这样呢？
大家不用去数这一共执行了多少次，因为算法时间复杂度与问题的大小无关（即与n的大小无关），不管这个常数是多少，我们都记作O(1)，而不能是O(4)，O（14）等其他任何数字。执行时间恒定的算法我们称之为具有O（1）的时间复杂度，又叫常数阶。
2.线性阶：考虑如下代码：

该循环的时间复杂度为O（n），因为循环体中的代码必须执行n次。
3.对数阶：考虑如下代码：

每次循环以后，count都会乘以2，因此循环会在（假设）x个2相乘大于n的时候退出。因此可以得到2^x = n，即x = log2(n)，所以这个循环的时间复杂度为O（logn）。
4.平方阶：两个都会循环n次的嵌套，时间复杂度自然就是O（n^2）。

如果是下面这种情况呢？
此时我们可以推导，外层循环执行第一次的时候内层循环执行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阶的推导并不难，难的是你对数列以及一些数学基本知识的应用以及掌握情况，也就是说他更多的考察你的数学能力。
（五）常见的时间复杂度

常见的时间复杂度的耗费时间的大小依次是O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n!)。
最坏情况运行时间：指运行时间不会再坏了，在应用中，这是一项最重要的需求，一般而言，除非特别指定，我们提到的运行时间都是最坏情况的运行时间。