【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

简介: 【数据结构】算法的复杂度分析:让你拥有未卜先知的能力

一、前言

一个程序能用很多不同的算法来实现,那么到底那种算法是效率最高的呢?
对此我们有两种方法:

第一种是事后统计法,既在编写之后,通过计时,比较不同算法编写的程序的运行时间,以此确定算法效率的高低。但是该方法的缺陷很大,会受到测试环境、数据规模的影响。

第二种是事前分析法,即在编写之前,依据一些统计方法对算法进行粗略估算,大致的估算出该算法的时间复杂度和空间复杂度,通过对比复杂度来评判那种算法的效率更高。

在这里插入图片描述
可以说,学会了如何分析一个算法的复杂度,就拥有了未卜先知的能力,即在这个算法被写出来之前,就能大致评判出这个算法的好坏。

二、时间复杂度

1、定义

维基百科:在计算机科学中,算法的时间复杂度(time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。

在这里插入图片描述

额......具体来举个例子吧。

void Func1(int N)
{
int count = 0;
// n*n次
for (int i = 0; i < N ; ++ i)
{
 for (int j = 0; j < N ; ++ j)
 {
 ++count;
 }
}
// 2*n次
for (int k = 0; k < 2 * N ; ++ k)
{
 ++count;
}
// 10次
int M = 10;
while (M--)
{
 ++count;
}
printf("%d\n", count);
}
AI 代码解读

这个函数一共执行的基本操作次数为:F(n)=n2+2n+10
但是,我们计算复杂度的时候,不一定需要计算这么精确的执行次数,我们只需要计算出大概的执行次数就行了,所以这里我们应该使用大O的渐进表示法。那么什么是大O表示法呢?

2、大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为(趋向于特定值或无穷大)的数学符号。

上面函数一共执行的操作次数为:F(n)=n2+2n+10
学过极限的都知道,当n趋向于无穷的时候,n2+2n+10 中的2n和10可以忽略不记。
所以用大O的渐进表示法,上面函数的时间复杂度应该为:O(n2)
**这里我们可以简单的总结一下方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
4、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。**

3、常见的时间复杂度

  • O(1)
一般情况下,要算法的执行时间不随问题规模 n 的增加而增大,那么就是O(1)的时间复杂度
void Func(int n)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}
AI 代码解读

以上代码看似存在循环,但是仔细看,当循环到第100次的时候,这个循环就停止了。
所以上面的时间复杂度为 O(1)

  • O(logn)
类似于二分查找、幂运算都是O(logn)的时间复杂度
void Func(int n)
{
 int i=1;
 while (i <= n)  
 {
   i = i * 2;
 }
}
AI 代码解读

以上代码,变量 i 从 1 开始,每循环一次就乘以 2。当大于n时,循环结束。所以,假设一共循环了x次,那么我们就可以得到:2x=nx=log2n ,忽略掉底数2,则该时间复杂度为:O(logn)

在这里插入图片描述

为什么可以忽略掉底数?
高中学过的换底公式:logbn=logbalogan
现在假设底数不是2是3,我们可以把log3n写成log32log2n,根据前面的规矩: 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。 而这里的log32是个常数,可以直接去除。所以兜兜转转,最后的时间复杂度还是O(logn)
  • O(nlogn)
void Func(int n)
{
    for (int i = 1; i <= n; i++)
    {
        int j = 1;
        while (j <= n)
        {
            j = j * 2;
        }
    }
}
AI 代码解读

根据上面可以知道,这个循环里面的循环的复杂度是O(logn),而这个循环又要执行n次,所以算下来,它的时间复杂度是O(nlogn)

  • O(n)
void Func(int n)
{
    for (int i = 1; i <= n; i++)
    {
        printf("我一共执行了n次哦!");
    }
}
AI 代码解读
  • O(n2)
循环套循环,每个循环都是n次
void Func(int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            printf("我一共执行了n*n次哦!");
        }
    }
}
AI 代码解读
  • O(mn)
void Func(int n,int m)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("看的出来我有那些不一样吗?");
        }
    }
}
AI 代码解读

在这里插入图片描述
确实还有其他很多不同的时间复杂度,比如,O(2n)O(n!)...但是这些时间复杂度都太高了,以至于高到很多计算机都承受不了,所以比较少见。

在这里插入图片描述
在这里插入图片描述

三、空间复杂度

1、定义

维基百科:在计算机科学中,一个算法或程序的空间复杂度定性地描述该算法或程序运行所需要的存储空间大小。空间复杂度是相应计算问题的输入值的长度的函数,它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似,空间复杂度通常也使用大O记号来渐进地表示例如O(n)O(nlogn)其中n用来表示输入的长度,该值可以影响算法的空间复杂度。

就像时间复杂度的计算不考虑算法所使用的空间大小一样,空间复杂度也不考虑算法运行需要的时间长短。

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

2、常见的空间复杂度

  • O(1)
无论 n 的值如何变化,代码在执行过程中开辟的内存空间是固定的
void Func(int n)
{
    int i = 0; int sum = 0;
    for (i = 1; i < n; i++)
    {
        sum = sum + i;
    }
}
AI 代码解读

这段代码之开辟了sum和i两个int类型的空间,大小是固定的。
所以这段代码的空间复杂度为O(1)

  • O(n)
随着n的值的增大,开辟的空间也逐渐增大
long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}
AI 代码解读

这段代码递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。
所以这段代码的空间复杂度为O(N)

  • O(n2)
  int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }
AI 代码解读

此处开辟的是一个二维数组,数组有n行,每行分别有1,2,3,...n列,所以是n(n+1)/2个元素空间,空间复杂度为n2

在这里插入图片描述

目录
打赏
0
0
0
0
24
分享
相关文章
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
91 1
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
76 29
|
14天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
49 2
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
68 20
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
49 6
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
99 1
阿里云先知安全沙龙(西安站) ——浅谈XSS漏洞挖掘与构造思路
本文介绍了DOM-XSS构造、运算符的威力和模板字符串妙用三个主题。通过多个实例图解,详细展示了如何利用DOM特性构造XSS攻击、JavaScript运算符在代码中的巧妙应用,以及模板字符串在开发中的灵活运用。这些内容对提升Web安全意识和编程技巧具有重要参考价值。
AI助理

你好,我是AI助理

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