算法效率,时间复杂度,空间复杂度.

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法效率,时间复杂度,空间复杂度.，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3001字，纯文字阅读大概需要5分钟。

内容图文

算法效率.

一般分为时间效率(时间复杂度),空间效率(空间复杂度)两种。

时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

时间复杂度

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一般来说想要准确了解一个算法的时间复杂度都需要上机测试之后才能得出结果.但现实中这就不可能实现.

但发现一个算法的时间复杂度与它的语句执行次数有关.(成正比)因此,便可以用算法的基本语句执行次数来表示算法的时间复杂度.

那么如何计算时间复杂度呢?

一般我们采用的是大O的渐进表示法.

步骤:

1、找到执行次数最多的语句

2、语句执行语句的数量级

3、用O表示结果

然后：

1、用常数1取代运行时间中的所有加法常数

2、在修改后的运行次数函数中，只保留最高阶项

3、如果最高阶项存在且不是1，那么我们就去除于这个项相乘的常数。比如5n^2我们取n^2.

例如:

void Func1(int N)
{
   int count = 0;
   for (int i = 0; i < N ; ++ i)
  {
     for (int j = 0; j < N ; ++ j)
     {
       ++count;//执行次数N^2
      }
  } 
  for (int k = 0; k < 2 * N ; ++ k)
  {
       ++count;//执行次数2*N

  }
  int M = 10;
  while (M--)
  {
    ++count;//执行次数M=10次
   }
      printf("%d\n", count);
}

执行次数:T(N)=N^2+2*N+10

再利用上面说的方法:就可以得出时间复杂度为O(N^2);

常见算法的时间复杂度排序

   O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

空间复杂度

  一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度计算规则也使用大O渐进表示法。

若一个算法为递归算法,其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数.

• 当一个算法的空间复杂度为一个常数，即不随被处理数据量n的大小而改变时，可表示为O(1)；
• 当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；
• 当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).

例:

1.冒泡排序算法

// 计算BubbleSort的空间复杂度？
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}

为开辟新的存储空间所以空间复杂度为O(1)

2.Fibonacci数列

// 计算Fibonacci的空间复杂度？
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray = new long long[ n+1]; //新开辟空间
fibArray[0] = 0;
fibArray[1] = 1;for (int i = 2; i <= n ; ++i)
{
fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
}
return fibArray ;
}

新开辟了n个空间,所以空间复杂度为O(n)

3.计算N!

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}

递归调用N次,开辟N个栈针,所以空间复杂度为O(N).

 

对于一个算法，其 时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间

 

 

内容总结

以上是互联网集市为您收集整理的算法效率,时间复杂度,空间复杂度.全部内容，希望文章能够帮你解决算法效率,时间复杂度,空间复杂度.所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---