算法的时间复杂度详解

前言

避免在处理大规模问题时出现效率低下，耗费较多资源，所以引入了算法复杂度，算法复杂度可以来衡量算法的效率和算法的可行性，可以帮助选择出最优的算法来解决问题；

时间复杂度的概念

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知
道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，而且每个人的机器不同，网络等因素的影响，不同时间地点所测出来的时间都不同，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
如下例一所示

例题一：

分析：

我们很容易知道

第一个 for循环 里面还嵌套了一个 for循环 ，总的会循坏执行N*N次；

第二个 for循环 会循环执行 2*N 次；

while循环 会执行10次；

所以** Func1** 执行的基本操作次数 ： N^2 +2*N +10

但是需要注意的是，实际中在计算时间复杂度时，并不是要计算出精确的执行的次数，而是只需要计算出大概次数，抓大头，这种表示方法叫大O渐近表示法（下面会详细讲解该方法的规则）

例如 N^2+2*N+10

当 N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

随着N越来越大，2N +10的值与N^2的值相比，2N +10的值的值太小，可以忽略，这里用大O渐近表示法 时间复杂度记为 O(N^2）

大O渐近表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数;
2、在修改后的运行次数函数中，只保留最高阶项;（例如上面的 N^2 + 2*N +10 中N的最高阶项为N^2 ）
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶；

(如2N^2 + N + 40 最高阶存在，为2N^2 ,用大O渐近表示法表示为 N^2 需要去除系数)

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
4，另外有些算法的时间复杂度存在最好、平均和最坏情况：（时间复杂度取最坏情况）
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)

例如：在一个长度为N数组中搜索一个数据x（例题代码下面例题4）
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N）

常见时间复杂度例题（含分析）

例一：

** 分析：**

第一个 for循环 循环了2*N 次

while循环 循环了10次

所以总的次数为 2*N -10

根据上面的规则2和3的 Func2的时间复杂度为 ：O(N) ；

例二：

** 分析：**

第一个for循环 循环了M次；

第二个for循环 循环了N次；

总的执行次数为 M+N 次

由于M与N的关系（大小关系c3的时间复杂度为 O(M+N)

如果题中说M>>N 则Func3的时间复杂度为 O(M)

              N>>M 则Func3的时间复杂度为 O(N)

如果M=N 则执行总次数为2M或则2M 所以时间复杂度为 O(M) 或则 O(N) （由上面的规则3）

例三：

** 分析：**

该算法只有一个for循环，执行了k=100次；

根据上面规则1可知，Func4的时间复杂度为 ： O(1)

例四：

分析：

strchr函数的作用是在一个字符串中找到目标字符在该字符串中第一次出现的位置，并返回该位置；

最好情况：1次找到                目标字符就在字符串的第一个元素；
 最坏情况：N次找到                目标字符在字符串的末尾；
平均情况：N/2次找到             

根据上面的规则4， strchr 的时间复杂度 为O(N)

例五：

分析：

由上述的代码易知，该算法为冒泡排序算法；

最好情况 当遍历完一遍时，没有元素的交换，即exchange为0，跳出循环 N次找到

最坏情况 全部元素都是无序的，则第一次遍历N次，第二次遍历N-1次，第三次遍历N-3次，以此类推，总的次数为 N+（N-1）+（N-2）…………+（2）=（ 2+N)*N/2 次

根据上面所述规则2，4可知 BubbleSort的时间复杂度为：O(N^2)

例六：

** 分析：**

由所示代码可知，该算法是二分查找法；

最好情况： 1次找到

最坏情况： 当查找所剩元素只有一个，或则查找完了还没找到该元素；

所以二分查找的时间复杂度为 O(log N)

例七：

分析：

当计算N的阶乘时，需要递归N次；

所以 阶乘递归的时间复杂度为 O(N)

例八：

** 分析：**

由图分析得 时间复杂度为 O(2^N)

本章完~ 空间复杂度的详解正在更新中

                                                                                                                   作者：GOTXX