时间复杂度计算方法以及常见的时间复杂度

���录

（）

 

零，前言

（）

一，时间复杂度的概念理解

二，时间复杂度的计算

三,常见的时间复杂度

1,常数阶

2,线性阶

3,对数阶

4,指数阶

5,根号阶

6,阶乘阶

---

 

零，前言

---

      时间复杂度衡量着一个程序的好坏，时间复杂度的估算是算法题的重中之重。但是很多初学者对于时间复杂度缺少一种概念，对于复杂程序的估算难以理解，理解不了时间复杂度，算法学习无从下手 。因此为了解决对时间复杂度的理解难题，本文将从简单到复杂介绍时间复杂度的计算方法，以及常见的时间复杂度，足以应付百分之八十的算法题。                                                   

一，时间复杂度的概念理解

---

    一般来说要确定算法的运行时间，只有你将他拿到机器上去测试一下才能确定，但是过于麻烦，那么有没有一种方法能够估算该算法的运行时间呢？因此引入了时间复杂度这个概念。

    时间复杂度是一种函数，定量地描述了该算法运行的时间。既然是一种函数，就涉及到自变量与因变量。因变量代表是时间复杂的规模，自变量是时间复杂度的执行时间。这里的执行时间并不是秒，分钟这类的具体时间  ，它表示的是一种“执行次数”。要想计算时间复杂度首先得找到该算法中的循环，算法中循环执行的次数就是算法的时间复杂度 。

     算法的时间复杂度的具体表示为：用大写的 O 来体现算法时间复杂度如O（f（n）），称之为 大 O 记数法。

 

二，时间复杂度的计算

---

      一，给定 n个元素 的数组a[n]，求其中 奇数 有多少个。

    判断一个数是偶数还是奇数，只需要求它除上 2 的余数是 0 还是 1，把所有数都判断一遍，并且对符合条件的情况进行计数，最后返回这个计数器就是答案，需要遍历所有的数，因此代码为：

int count(int n, int a[]) {    int cnt = 0;    for(int i = 0; i  
由代码段知，该函数中只有一层for循环，而该循环执行了n次，因此时间复杂度为O（N）；
 
二，求下面函数的时间复杂度
 
int fun(int n){   int cnt = 0;  for(int i = 0;i