数据结构之时间复杂度和空间复杂度

简介: 数据结构之时间复杂度和空间复杂度

前言

我们都知道算法是处理数据的方法,那么如何衡量一个算法的好坏呢?(即,判断该算法的效率如何)

由于算法在编写成可执行程序后,运行会消耗时间资源和空间(内存)资源,因此衡量一个算法的好坏一般通过时间和空间两个维度进行衡量。即,时间复杂度和空间复杂度

一、时间复杂度

1.时间复杂度是什么?

时间复杂度是衡量一个算法运行的快慢。

2.如何计算时间复杂度?

找到某条基本语句与问题n之间的数学函数关系,就是找到了算法的时间复杂度。即,算法的时间复杂度本质上是一个数学的函数表达式。

1.时间复杂度计算的是算法运行所用的时间(单位:s)吗?

如果是第一次听说算法的时间复杂度,应该会片面的认为是计算一个算法运行所需要的时间。然而实际上由于机器的性能不同,以及一些不可控因素影响,一个算法运行的具体时间是无法计算出的(即,同一个算法在不同编译器上运行的时间是不一定相同的)。

那么我们该如何衡量一个算法的运行快慢呢?我们注意到算法的运行时间与算法中语句的执行次数是成正比例的,因此我们就把算法中基本操作的执行次数作为算法的时间复杂度

2.时间复杂度是算具体的执行次数吗?

先看一个题(注释中标注了语句的执行次数)。

// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N) //N*N + 2*N + 10
{
  int count = 0;
  for (int i = 0; i < N; ++i)  //N*N
  {
    for (int j = 0; j < N; ++j)  //N
    {
      ++count;
    }
  }
  for (int k = 0; k < 2 * N; ++k) //2*N
  {
    ++count;
  }
  int M = 10;
  while (M--) //10
  {
    ++count;
  }
  printf("%d\n", count);
}

我们不难计算出,Func执行的基本操作的次数为:

F(N) = NN+2N+10

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) =1002010

可以看到当N 越大,后面两项对总数的影响就越小,N无限大时,后面两项可以忽略不计。

因此实际计算时,我们不一定要计算精确的执行次数,只需要一个大概的估算即可表示算法的时间复杂度即可。

3.如何估算时间复杂度?(大O的渐进表示法)

1.大O符号(Big O notation):是用于描述函数渐进行为的数学符号。

大O的渐进表示法:(规则)

1.用常数1代替运行时间中所以加法常数

2.在修改后的运行次数中只保留最高次数项

3.如果最高次数项存在,并且不是1,则去除与最高次数项的系数

用大O的渐进表示法可以大致的表示出算法的大概量级。

可以直接看出,用大O渐进表示法以后,Func的时间复杂度为O(n^2)。

3.特殊的时间复杂度

有一些算法存在:最坏情况、最好情况和平均情况。

例如,在N个数中找最大的数

我们很容易知道,最坏情况是找n次,平均情况找n/2次,最好情况找1次

但是实际中,一般关注最坏运行情况(悲观保守的预估),因此这个查找的方法时间复杂度为O(n)。

4.时间复杂度的对数表示

计算时间复杂度时会出现有以二为底n的对数这种情况,具体有以下两种表示(图中绿色框里的)

一般情况下的对数都是以2为底的对数,所以简写也只针对以2为底。其他底数的对数形式没有简写,也很少出现。

二、空间复杂度

1.空间复杂度是什么?

空间复杂度是衡量一个算法运行所需要额外开辟的空间

2.如何计算空间复杂度?

本质上也是一个函数表达式,用来计算算法的空间效率

1.空间复杂度计算的是算法运行所开辟的空间(单位:bite)吗?

1.首先,空间复杂度计算的不是程序在运行过程中总共开辟的空间,而是临时(额外)开辟的空间(所谓额外,就是指不包括原有的空间)只需要计算这个算法所需要的额外空间即可。

2.其次,空间复杂度不是计算不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。

注意:

1.函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运的得时候申请的额外空间来确定。

2.在栈区或者堆区开辟的额外空间都要计算上。

2.空间复杂度是算具体的变量数吗?

空间复杂度计算规则基本跟时间复杂度类似,也是使用大O渐进表示法,只需要计算出它大概属于哪个量级即可。(时间复杂度中已经介绍过大O的渐进表示法,这里就不再赘述了)

实际上,目前我们更关注时间复杂度,不太关注空间复杂度,原因可以参考摩尔定律。因为目前的机器内存空间都比较大,所有可以不太注重(但是也不能耗费太多)。

摩尔定律:摩尔定律是英特尔创始人之一戈登·摩尔的经验之谈,其核心内容为:集成电路上可以容纳的晶体管数目在大约每经过18个月到24个月便会增加一倍。换言之,处理器的性能大约每两年翻一倍,同时价格下降为之前的一半。

三、常见的复杂度对比(含图)

例子 复杂度(大O渐进表示法) 量级
5201314 O(1) 常数阶
3n+4 O(n) 线性阶
3n^2+4n+5 O(n^2) 平方阶
3logn+4 O(logn) 对数阶
2n+3nlogn+14 O(nlogn) nlogn阶
n^3+2n+6 O(n^3) 立方阶
2^n O(2^n) 指数阶

对比图如下:

可以看出时间复杂度虽然不能直接表示出算法运行所需的时间,但是可以对比出不同算法的效率高低。

注意

1.计算时间复杂度不能直接数循环,要根据算法的逻辑来计算。

2.空间是可以重复利用的,不用累计;(递归过程中/循环过程中,一些在栈区开辟的空间经过函数栈帧的创建与销毁,这些空间是可以重复利用的) 而时间是一去不复返的,需要累计。(时间是不能重复利用的)

总结

以上就是今天要讲的内容,本文主要介绍了衡量一个算法好坏的方法,即算法的时间复杂度和空间复杂度,同时还介绍了如何计算复杂度以及一些常见复杂度的对比

本文作者也是一个正在学习编程的萌新,目前也只是刚开始接触数据结构这方面的内容,如果有什么内容方面的错误或者不严谨,欢迎大家在评论区指出。

最后,如果本篇文章对你有所启发的话,也希望可以支持支持作者,谢谢大家!

相关文章
|
6月前
|
算法 搜索推荐 程序员
数据结构中时间复杂度的介绍
冒泡排序是通过重复遍历数组,比较并交换相邻元素来排序数组的。因为它包含两层嵌套循环,每层循环的最大迭代次数近似于n,所以时间复杂度是O(n²)。 通过上述分析,我们可以看到不同代码结构对算法性能有着显著的影响。在设计数据结构和算法时,理解并计算时间复杂度是非常重要的,它帮助程序员选择或优化算法,以处理更大的数据集或提高程序的运行速度。
42 2
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
33 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
6月前
|
存储 算法 C语言
数据结构中的空间复杂度
优化空间复杂度对于提升程序性能和资源利用率至关重要,特别是在资源受限的环境(如嵌入式系统和移动设备)中。高效的数据结构和算法设计可以显著提升程序的执行效率和可扩展性。 综上所述,理解和优化空间复杂度是设计高效数据结构和算法的关键。通过分析常见数据结构的空间复杂度,并结合实际代码示例,我们可以更好地理解这一重要概念,并在实际编程中应用这些知识。希望本文能帮助你更好地掌握空间复杂度及其在数据结构中的应用。
46 2
|
2月前
|
机器学习/深度学习 存储 算法
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
【初阶数据结构】算法效率大揭秘 | 时间与空间复杂度的深度剖析
|
2月前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
15 0
|
4月前
|
存储 算法
【数据结构】——时间复杂度与空间复杂度
【数据结构】——时间复杂度与空间复杂度
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6月前
|
机器学习/深度学习 算法
数据结构入门 时间 空间复杂度解析
数据结构入门 时间 空间复杂度解析
35 0
|
6月前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
38 0