如何评判算法好坏?复杂度深度解析

简介: 如何评判算法好坏?复杂度深度解析

1. 算法效率


1.1 如何衡量一个算法好坏

long long Fib(int N)
{
  if (N < 3)
  {
    return 1;
  }
  return Fib(N - 1) + Fib(N - 2);
}

斐波那契数列的递归方式非常简洁,但简介一定好吗?那该如何衡量其好与坏呢?


1.2 算法的复杂度

算法在编写成可执行程序后,运行时需要消耗时间资源和空间(内存)资源,因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,及时间复杂度空间复杂度

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


2 时间复杂度


2.1 时间复杂度的概念

时间复杂度的概念:在计算机科学中,算法的时间复杂度是一个函数,他定量描述了该算法的运行时间。

一个算法的运行时间,从理论上说是算不出来的,只有把你的程序放在机器上跑起来,才知道。但是我们需要每个算法都上机测试吗?

是都可以上机,但是这很麻烦,所以才有了时间复杂度这个分析方法。

一个算法所发费的时间和其中的语句执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度

即,找到某条语句与问题规模N之间的数学表达式,就是该算法的时间复杂度。


2.1.1 实例

我们先来看看这段代码:

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);
  return 0;
}

Func1的执行次数:F(N)= N^2 + 2*n + 10

但在实际计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概的执行次数即可,那么这里我们就要用到大O的渐进表示法


2.2 大O的渐进表示法

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

推导大O阶方法:

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

②: 在修改后的运行次数函数中,只保留最高阶项。

③: 如果最高阶存在并且不是1,则去掉与这个项相乘的常数,得到的结果就是大O阶。

④: 有一些算法存在最好、最坏和平均的情况,但实际中一般关注的是算法的最坏运行情况。

所以使用大O的渐进表示法以后,Func1的时间复杂度为O(N^2).

通过上面我们很容易发现大O的渐进表示法去掉了那些对结果印象不大的项,简洁明了的表示执行次数。(本质上是计算属于那个量级


2.3 常见时间复杂度计算举例

实例1:

// 计算Func2的时间复杂度?
void Func2(int N)
{
 int count = 0;
 for (int k = 0; k < 2 * N ; ++ k)
 {
 ++count;
 }
 int M = 10;
 while (M--)
 {
 ++count;
 }
 printf("%d\n", count);
}

3 空间复杂度

空间复杂度也是一个函数表达式,是对一个算法在运行过程中临时占用存储空间大小的量度

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

空间复杂度的计算规则基本和时间复杂度的计算类似,也用大O的渐进表示法

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


4 常见复杂度对比

一般算法的常见复杂度如下:


5 结尾

本篇博客到此就结束了。如果对你有帮助,记得三连哦。感谢您的支持!!!


目录
打赏
0
0
0
0
10
分享
相关文章
如何控制上网行为——基于 C# 实现布隆过滤器算法的上网行为管控策略研究与实践解析
在数字化办公生态系统中,企业对员工网络行为的精细化管理已成为保障网络安全、提升组织效能的核心命题。如何在有效防范恶意网站访问、数据泄露风险的同时,避免过度管控对正常业务运作的负面影响,构成了企业网络安全领域的重要研究方向。在此背景下,数据结构与算法作为底层技术支撑,其重要性愈发凸显。本文将以布隆过滤器算法为研究对象,基于 C# 编程语言开展理论分析与工程实践,系统探讨该算法在企业上网行为管理中的应用范式。
91 8
解析公司屏幕监控软件中 C# 字典算法的数据管理效能与优化策略
数字化办公的时代背景下,企业为维护信息安全并提升管理效能,公司屏幕监控软件的应用日益普及。此软件犹如企业网络的 “数字卫士”,持续记录员工电脑屏幕的操作动态。然而,伴随数据量的持续增长,如何高效管理这些监控数据成为关键议题。C# 中的字典(Dictionary)数据结构,以其独特的键值对存储模式和高效的操作性能,为公司屏幕监控软件的数据管理提供了有力支持。下文将深入探究其原理与应用。
61 4
员工上网行为监控软件中基于滑动窗口的C#流量统计算法解析​
在数字化办公环境中,员工上网行为监控软件需要高效处理海量网络请求数据,同时实时识别异常行为(如高频访问非工作网站)。传统的时间序列统计方法因计算复杂度过高,难以满足低延迟需求。本文将介绍一种基于滑动窗口的C#统计算法,通过动态时间窗口管理,实现高效的行为模式分析与流量计数。
75 2
内网监控桌面与 PHP 哈希算法:从数据追踪到行为审计的技术解析
本文探讨了内网监控桌面系统的技术需求与数据结构选型,重点分析了哈希算法在企业内网安全管理中的应用。通过PHP语言实现的SHA-256算法,可有效支持软件准入控制、数据传输审计及操作日志存证等功能。文章还介绍了性能优化策略(如分块哈希计算和并行处理)与安全增强措施(如盐值强化和动态更新),并展望了哈希算法在图像处理、网络流量分析等领域的扩展应用。最终强调了构建完整内网安全闭环的重要性,为企业数字资产保护提供技术支撑。
86 2
基于 C++ 哈希表算法的局域网如何监控电脑技术解析
当代数字化办公与生活环境中,局域网的广泛应用极大地提升了信息交互的效率与便捷性。然而,出于网络安全管理、资源合理分配以及合规性要求等多方面的考量,对局域网内计算机进行有效监控成为一项至关重要的任务。实现局域网内计算机监控,涉及多种数据结构与算法的运用。本文聚焦于 C++ 编程语言中的哈希表算法,深入探讨其在局域网计算机监控场景中的应用,并通过详尽的代码示例进行阐释。
82 4
员工电脑监控场景下 Python 红黑树算法的深度解析
在当代企业管理范式中,员工电脑监控业已成为一种广泛采用的策略性手段,其核心目标在于维护企业信息安全、提升工作效能并确保合规性。借助对员工电脑操作的实时监测机制,企业能够敏锐洞察潜在风险,诸如数据泄露、恶意软件侵袭等威胁。而员工电脑监控系统的高效运作,高度依赖于底层的数据结构与算法架构。本文旨在深入探究红黑树(Red - Black Tree)这一数据结构在员工电脑监控领域的应用,并通过 Python 代码实例详尽阐释其实现机制。
82 7
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
76 0
基于 C# 的内网行为管理软件入侵检测算法解析
当下数字化办公环境中,内网行为管理软件已成为企业维护网络安全、提高办公效率的关键工具。它宛如一位恪尽职守的网络守护者,持续监控内网中的各类活动,以确保数据安全及网络稳定。在其诸多功能实现的背后,先进的数据结构与算法发挥着至关重要的作用。本文将深入探究一种应用于内网行为管理软件的 C# 算法 —— 基于二叉搜索树的入侵检测算法,并借助具体代码例程予以解析。
76 4
JS数组操作方法全景图,全网最全构建完整知识网络!js数组操作方法全集(实现筛选转换、随机排序洗牌算法、复杂数据处理统计等情景详解,附大量源码和易错点解析)
这些方法提供了对数组的全面操作,包括搜索、遍历、转换和聚合等。通过分为原地操作方法、非原地操作方法和其他方法便于您理解和记忆,并熟悉他们各自的使用方法与使用范围。详细的案例与进阶使用,方便您理解数组操作的底层原理。链式调用的几个案例,让您玩转数组操作。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
深入理解HTTP/2:nghttp2库源码解析及客户端实现示例
通过解析nghttp2库的源码和实现一个简单的HTTP/2客户端示例,本文详细介绍了HTTP/2的关键特性和nghttp2的核心实现。了解这些内容可以帮助开发者更好地理解HTTP/2协议,提高Web应用的性能和用户体验。对于实际开发中的应用,可以根据需要进一步优化和扩展代码,以满足具体需求。
409 29

热门文章

最新文章

推荐镜像

更多
  • DNS
  • AI助理

    你好,我是AI助理

    可以解答问题、推荐解决方案等

    登录插画

    登录以查看您的控制台资源

    管理云资源
    状态一览
    快捷访问