时间复杂度与空间复杂度详解

简介: 时间复杂度与空间复杂度详解

一、算法效率

1.1 如何衡量一个算法的好坏

  • 我一直有个问题,算法到底如何比较,如何衡量一个算法的好坏?
  • 我的理解:


  • 思路巧妙,神来之笔!


枯燥的代码,却带着无限的智慧,也是这智慧让程序员在学习过程中一次次惊呼:妙哉!此法妙哉!!所以对我而言,一个奇巧的思路是竞赛衡量的一个标准(主观感受)


  • 时间、空间资源利用!


一串好的算法代码不一定是简洁的,但一定是空间、时间资源占用少的。


1.2 算法的复杂度

  • 算法在编写成可执行程序运行时,需要耗费时间资源和空间资源,因此衡量一个算法的好坏,是从时间和空间两个维度上衡量的,即时间复杂度和空间复杂度。
  • 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间大小。

二、时间复杂度

2.1 时间复杂度的定义

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。


举个例子:

// 请计算一下Func1中++count语句总共执行了多少次?
void Func1(int N)
{
  int count = 0;
  for (int i = 0; i < N ; ++ i)
  {
    for (int j = 0; j < N ; ++ j)
    {
      ++count;
    }
  }

  for (int k = 0; k < 2 * N ; ++ k)
  {
    ++count;
  }

  int M = 10;
  while (M--)
  {
    ++count;
  }

  printf("%d\n", count);
}

Func1 执行的基本操作次数 :

  • N = 10 F(N) = 130
  • N = 100 F(N) = 10210
  • N = 1000 F(N) = 1002010

根据上述带入尝试,我们不难得出Func1执行的基本操作次数是下面这个函数表达式:

F(N)=N2+2∗N+10(数学表达式)

在实际计算中,我们并不会计算精准的次数,一般采取估算量级,所以我们会使用大O的渐进表示法


2.2 大O的渐进表示法

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


推导大O阶方法:


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


2、在修改后的运行次数函数中,只保留最高阶项(高数极限思想)。


3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。


使用大O的渐进表示法以后,Func1的时间复杂度为:

O(N2+2∗N+10)−−>O(N2)

总结一下: 大O渐进表示法主要是记录复杂度量级,去掉了那些对结果影响不大的项。


2.3 如何记录表示算法复杂度

一个算法运行过程往往有三种衡量记录情况:


最坏情况: 任意输入规模的最大运行次数(上界)


平均情况: 任意输入规模的期望运行次数


最好情况: 任意输入规模的最小运行次数(下界)


所以可以描述一个算法的复杂度范围,来表示算法的复杂度范围,但实际中我们往往采用最坏的情况来表示记录一个算法的复杂度(我也喜欢,因为每一次运行都只会有惊喜!!!)


三、空间复杂度

3.1 空间复杂度的定义

  • 空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度(额外空间大小) 。
  • 空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。


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


3.2 小试牛刀

实例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;
  }
}

实例1:我们必须明确的是:空间复杂度记录的是额外的临时变量空间大小,因此我们再看实例1的时候,只会计算end、exchange、i等临时变量大小即可。不用计算数组a开辟的空间大小。所以这里空间复杂度就是O(1);

实例2:

// 计算Fibonacci的空间复杂度?
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{
 if(n==0)
      return NULL;

 long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
 fibArray[0] = 0;
 fibArray[1] = 1;
 for (int i = 2; i <= n ; ++i)
 {
     fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }

 return fibArray;
}

实例2:这里相当于malloc,创建了n+1个临时空间大小,因此也非常简单,这里空间复杂度也就是O(N)。

这就是最基本的。空间复杂度相较于时间复杂度要简单很多,通常不是O(N)就是O(1)。

相关文章
|
算法 C语言 网络架构
Cisco Packet Tracer入门篇
文章目录 一、什么是Packet Tracer? 二、操作界面 1.连接线 2.交换机 3.路由器 4.终端设备 三、接口分类 四、简单案例入门 1.建立拓扑 2.配置pc端ip 3.Ping测试
|
存储 缓存 Linux
SMB小传 —— SMB网络文件系统协议介绍
SMB网络文件系统协议, 全名服务器消息块(Server Message Block),曾用名CIFS(通用互联网文件系统 Common Internet File System), 公元1983年诞生于IBM[1],幼年得到英特尔和微软的照料,最终在微软的培养下成长为当今世上网络文件系统协议两极之一的存在。
20912 0
|
消息中间件 存储 算法
深度揭秘!Kafka和ZooKeeper之间的相爱相杀
**摘要:** 本文介绍了Kafka和ZooKeeper的角色及其关系。Kafka是分布式流处理平台,用于实时数据管道和流应用;ZooKeeper是分布式协调服务,处理同步和集群协调。在Kafka中,ZooKeeper存储元数据,管理集群成员,选举Controller。随着KIP-500提案,Kafka计划移除对ZooKeeper的依赖,转向基于Raft的共识机制,以简化架构、提高性能和一致性。此外,文章提到了etcd作为基于Raft的元数据存储系统的应用。本文旨在帮助读者理解ZooKeeper在Kafka面试中的重要性,并了解Kafka的未来发展方向。
1634 2
|
10月前
|
网络协议 Linux 虚拟化
如何在 Linux 系统中查看进程的详细信息?
如何在 Linux 系统中查看进程的详细信息?
858 1
|
SQL 人工智能 Java
mybatis-plus配置sql拦截器实现完整sql打印
_shigen_ 博主分享了如何在MyBatis-Plus中打印完整SQL,包括更新和查询操作。默认日志打印的SQL用?代替参数,但通过自定义`SqlInterceptor`可以显示详细信息。代码示例展示了拦截器如何替换?以显示实际参数,并计算执行时间。配置中添加拦截器以启用此功能。文章提到了分页查询时的限制,以及对AI在编程辅助方面的思考。
1910 5
mybatis-plus配置sql拦截器实现完整sql打印
|
关系型数据库 MySQL Linux
MySQL - \g 和 \G用法与区别
MySQL - \g 和 \G用法与区别
304 1
|
算法 编译器
什么是时间复杂度?
什么是时间复杂度?
644 0
|
存储 数据可视化 Cloud Native
用Ganos低代码实现免切片遥感影像浏览(二):动态栅格瓦片
本文介绍了Ganos全新发布了动态栅格瓦片能力,帮助用户将库内栅格数据或栅格分析结果快速可视化,无需依赖类似GeoServer等空间服务中间件,技术栈短平快,使用灵活高效。
|
编译器 C语言 C++
【C语言】strcpy()函数(字符串拷贝函数详解)
【C语言】strcpy()函数(字符串拷贝函数详解)
698 1
|
Kubernetes 调度 容器
Kubernetes容器资源限制
Kubernetes容器资源限制
239 0