时间复杂度、空间复杂度

▲复杂度

时间复杂度：评估执行程序所需的时间。可以估算出程序对处理器的使用程度。递归总次数*每次递归中基本操作执行的次数

空间复杂度：评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。临时占用存储空间的度量

 

设计算法时，时间复杂度要比空间复杂度更容易出问题，所以一般情况一下我们只对时间复杂度进行研究。一般面试或者工作的时候没有特别说明的话，复杂度就是指时间复杂度。

 

 

时间复杂度：

时间复杂度实际上是一个函数，代表基本操作重复执行的次数，进而分析函数虽变量的变化来确定数量级，数量级用O表示，所以算法的时间复杂度为：

T（n）=O（f（n））；

在一个算法存在最好、平均、最坏三种情况，我们一般关注的是最坏情况，原因是，最坏情况是任何输入实例在运行时间的上界，对于某些算法来说，最坏情况出现的比较频繁，从大体上来看，平均情况和最坏情况一样差。

一般O（n）的计算方法：

—用1代替所有运行时间中出现的加法常数；

—在修改后的运行函数中保留最高阶的项；

—如果最高阶的项系数不是1，则去除这个项系数。

递归算法的时间复杂度为：递归总次数*每次递归中基本操作执行的次数

空间复杂度(Space Complexity)：S（n）=O（f（n））；

是对一个算法在运行过程中临时占用存储空间的度量，一个算法在计算机存储器上所占用的存储空间包括存储算法本身所占用的空间，算数和输入输出所占用的存储空间以及临时占用存储空间三个部分，算法的输入输出数据所占用的存储空间是由待解决的问题来决定的，通过参数表由调用函数而来，它随本算法的不同而改变，存储算法本身所占用的存储空间有算法的书写长短成正比。算法在运行过程中占用的临时空间由不同的算法决定。

常数时间 O(1)，对数时间 O(log n)，线性时间 O(n)，线性对数时间 O(n log n)，平方时间 O(n^2)

int x = 90;
     int y = 100;
     while (y > 0)
     {
          if (x > 100)
          {
              x = x - 10;
              y--;
          }
          else
          {
              x++;
          }
     }

 

时间复杂度：O(1)【循环常数100次】，空间复杂度：O(1)【只有两个临时变量】;

2、当有若干个循环时，时间复杂度是和嵌套层数最多的循环语句中最内层的频度决定的

for (i = 0; i < n; i++)
     {
          for (j = 0; j < i; j++)
          {
              for (k = 0; k < j; k++)
              {
                   x++;
              }
          }
     }

 

时间复杂度：O(n^3)【循环常数n*i*k次】,空间复杂度：O（1）【只有1个临时变量】

3、求二分法的时间复杂度

int select(int a[], int k, int len)
{
     int left = 0;
     int right = len - 1;
     while (left <= right)
     {
          int mid = left + ((right - left) >> 2);
          if (a[mid] == k)
          {
              return 1;
          }
          else if (a[mid] > k)
          {
              right = mid - 1;
          }
          else
          {
              left = mid + 1;
          }
     }
     return NULL;
}

 

分析：

 

在最坏的情况下循环x次后找到，n/（2^x）=1;x=log2n;

所以二分查找的时间复杂度为：O（log2n）【基本操作次数】；空间复杂度O（1）【只有1个临时变量】；

对数时间的所在地常见以二分查找为代表。

4、用递归算法求n的阶乘

int fac(int n)
{
     if (n <= 2)
     {
          return n;
     }
     else
     {
          return fac(n - 1)*n;
     }
}

 

n的阶乘的时间复杂度很简单：就是n次递归算法，所以为O（n）【循环n次】，空间复杂度O（n）【嵌套方法中临时变量n个】，递归的深度是n。

常数阶O(1)
对数阶O(log2n)
线性阶O(n)
线性对数阶O(nlog2n)
平方阶O(n2)
立方阶O(n3)
k次方阶O(nk)
指数阶O(2n)

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。