在介绍复杂度之前我们现分享一个名词叫算法效率。
算法效率：算法效率是指算法执行的时间，算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。
算法效率也分为两种： 一种是时间效率，一种是空间效率，也被称为时间复杂度和空间复杂度。
时间复杂度主要衡量的是一个算法的运行速度。
空间复杂度主要衡量一个算法所需要的额外空间。(随着科学技术的发展现在的空间复杂度已经显得不这么重要了，我们现在一般更注重运行速度)
时间复杂度不计算时间，计算大概的运算次数。
空间复杂度不计算空间，计算大概定义的变量个数。
1.时间复杂度定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间. 一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度.
首先我们来看一段代码：
Func1执行的基本操作次数: F(N) = N^2 + 2*N + 10
实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
大O符号:是用于描述函数渐进行为的数学符号。
那我如何推导大O阶方法那？
基于一下三个规则：
1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中,只保留最高阶项。
3.如果最高阶项存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶。
再举几个例子：
可以看到，这几个简单的例子都是基于以上三个规则所计算出的时间复杂度。
但是，如果我写的一个代码是一个数组，我需要在里面查找出一个数字，最好的情况就是一下子查找到，最坏的情况就是最后一个才找到，还有在中间找到的情况，循环的次数不确定怎么办？
这是我们遵循最坏运行情况：若最坏需要检索N次，则此时的时间复杂度就为O(N)。
基于上面的理论，我们再来看一下耳熟能详的冒泡排序：
实际上，我们所说的时间复杂度就是代码的运行次数。
那好，根据冒泡排序的逻辑：从第一个数字开始，和第二个数字比较，若第二个数字大于第一个数字，则交换两个数字的位置，以此类推。但我们在写代码的时候的逻辑是一趟一趟的进行循环，先交换完第一趟，然后再折返回来进行第二趟的比较交换。
我们可以知道准确的时间复杂度为：F(N) = n-1 + n-2 + … + 2 + 1,即：1到n-1的等差数列求和。用大O渐进法表示也就是O(N^2)
但实际上我们真的需要排序这么多次吗？
可以看到代码中有一个exchange，我们把它称作Flag，只有在判断if条件语句成立的时候才会将exchange置为1，否则就跳出了循环，并执行了下面的break语句。
可见，我们上面计算的时间复杂度O(N^2)是最坏的结果，而最好的结果只需要排序一次足矣，即O(N)，但我们依然取最坏的结果为公认的时间复杂度。
下面，再给出几个代码，有兴趣的同学可以自己尝试下算算这几个代码的时间复杂度。
1.二分查找
2.阶乘递归
3.斐波那契递归
算过之后，是不是发现，如果仅仅依靠代码来计算时间复杂度，往往是不切实际的。
所以我们真正要做到的是根据代码的逻辑思想和所要表达出的意思，来计算时间复杂度。
下面揭晓答案：三个代码的时间复杂度分别为O(logN),O(N)，O(2^N)。
2.空间复杂度定义：
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没有太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
还是那个冒泡排序:
计算一下它的空间复杂度
它定义的变量有:a,n,end,exchange,i五个变量
所以他的空间复杂度为O(1),为常数个变量
再看一个:
空间复杂度为O(N)。
以上就是全部内容了，有错误或者问题欢迎随时补充和提问。
