如何理解算法时间复杂度

这篇文章主要讲解了“如何理解算法时间复杂度”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“如何理解算法时间复杂度”吧！

我们可以用下面的表达式来表示：

通常主要有以下几种表达式来描述时间复杂度：

• O(1)：常量时间

• O(n)：线性时间

• O(log n)：对数时间

• O(n^2)：二次方时间

• O(2^n)：指数时间

• O(n!)：阶乘时间

每种时间复杂度有所不同，下面我们一起来详细了解这几种时间复杂度。

大O复杂度

O(1)

O(1)表示常量时间复杂度，当给定大小为n的输入，无论n为何值，最后算法执行的时间是个常量。举个例子：

int func(int n) {     n++;     return n*2; }

上面的程序中，无论输入n的值如何变化，程序执行时间始终是个常量。我们简化处理一下，假如函数中每行语句的执行时间是1，则执行时间的数学表达式：

无论n为多大，最后的执行时间都是2这个固定值。虽然是运行时间为2，但是这里我们也用O(1)来表示，这里的1代表是一个常数。

O(n)

O(n)表示线性时间复杂度，算法的执行时间随着输入n的大小成线性变化。

int func(int n) {     int sum = 0;     for(int i=0; i<n; i++)     {         sum = sum + i;     }      return sum; }

上面的这个程序中，函数的执行时间随着n的变化成线性的关系。

对于这种可以用线性表达式表示的情况，我们用O(n)来表示。

为什么可以省略掉表达式中的其他系数呢?主要是当n趋近于无穷大时，系数相对于无穷大的n来说可以忽略不计。

O(n^2 )

O(n^2)表示二次方时间复杂度，一个算法的时间将会随着输入数据n的增长而呈现出二次关系增加。

int func(int n) {     int sum = 0;     for(int i=0; i<n; i++)     {         for(int j=0; j<n; j++)         {             sum = sum + i + j;         }     }      return sum; }

上面的程序中，是个两层循环的程序，函数的执行时间和n是二次方的关系：

对于这种类型的程序，我们可以用O(n^2)表示。不过，循环嵌套除了这种两层循环之外，还会有三层、四层...n层循环，对应的其复杂度就是O(n^3)  、O(n^4)...O(n^n)。

O(2^n)

O(2^n)表示指数复杂度，随着n的增加，算法的执行时间成倍增加，它是一种爆炸式增长的情况。

int func(int n) {     if(n==0) return 1;      return func(n) + func(n-1) }

上面的代码中，有两次递归调用，函数的执行时间就会和输入n成指数的关系。

因此，这里我们可以用O(2^n)表示。

O(log n)

O(log  n)表示对数时间复杂度，算法执行时间和n是一种对数关系。这种类型的算法会在执行的过程中，随着程序的执行其完成某个功能的操作步骤越来越少。其中，我们所熟知的二分查找法就是一个很好的例子。比如，下面这个代码在一个有序列表中查找某个值的位置，我们通过二分法进行查找。

int func(int a[], int size, int num) {     int left = 0;     int right = size-1;      while(left <= right)     {         int mid = (left + right)/2;          if(a[mid] > num)         {             right = mid - 1;         }         else if (a[mid] < num)         {             left = mid + 1;         }         else         {             return num;         }     }      return -1; }

在最糟糕的情况下，我们通过二分法拆分x次后，最后一个元素就是我们要找的元素。我们可以得到下面的等式：

函数运行时间可以表示为：

因此，这里我们可以用O(log n)表示。

O(n!)

对于阶乘关系的复杂度，最典型的例子就是旅行商问题。

假设有一个旅行商人要拜访n+1个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。

这个问题最简单的方法是通过穷举法列出所有的排列组合。如果有n+1个城市，根据我们数学中学过的排列组合计算方法，可以算出所有组合数为n!，所以这种穷举法对应的时间复杂度也就是O(n!)了。

感谢各位的阅读，以上就是“如何理解算法时间复杂度”的内容了，经过本文的学习后，相信大家对如何理解算法时间复杂度这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！