欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 资讯 > [数据结构]算法复杂度详解

[数据结构]算法复杂度详解

2024/12/27 7:41:37 来源:https://blog.csdn.net/2301_79450966/article/details/142320915  浏览:    关键词:[数据结构]算法复杂度详解

文章目录

  • 一、引言
    • 1、想象数据结构与算法的奇妙世界
    • 2、算法复杂度的轻松解读
    • 3、数据结构与算法的温馨寄语
  • 二、轻松掌握复杂度基础
    • 1、时间复杂度:算法速度的衡量尺
    • 2、空间复杂度:算法占地的衡量尺
    • 3、常见的复杂度
  • 三、复杂度的计算
    • 1、时间复杂度计算
    • 2、空间复杂度计算
    • 3、最好、最坏、平均复杂度
  • 四、C语言中的复杂度分析实例
    • 1、求和函数
    • 2、冒泡排序
    • 3、矩阵乘法
    • 4、递归计算斐波拉契数
  • 五、扩展阅读

一、引言

1、想象数据结构与算法的奇妙世界

想象一下,数据结构就像书架,让数据变得有序。算法则是聪明的管理员,能快速找到你需要的数据。简单来说,算法就是帮我们把数据变成有用信息的聪明方法。

2、算法复杂度的轻松解读

算法复杂度就像问管理员找书快不快,需要多大地方放书。时间复杂度是找书速度,空间复杂度是书架大小。在编程中,这就像优化工作流程,让代码更快,占用资源更少。

3、数据结构与算法的温馨寄语

无论你是编程新手还是资深程序员,数据结构和算法都是你的好朋友。它们是计算机科学的基础,也是你写出高效、可靠代码的秘密武器。掌握它们,就像给编程加速,让代码更流畅、更高效。它们也是你展现才华的舞台,在笔试和面试中证明你的能力。


二、轻松掌握复杂度基础

1、时间复杂度:算法速度的衡量尺

时间复杂度,就是估算算法跑多快的一个工具。它不看具体时间,而是看算法里基本操作做了多少次,和数据量有啥关系。就像看厨师做菜,不看具体几分钟,而是看食材多少来估时间。

2、空间复杂度:算法占地的衡量尺

空间复杂度,是看算法运行时占多少地方的一个工具。它不算具体的bytes,而是算用了多少变量,就像看房间里放了多少箱子。主要关注的是算法临时申请的空间,编译时定好的栈空间不算。

3、常见的复杂度

  • 常数复杂度 O(1):算法执行时间恒定,不受数据量大小影响,效率极高。
  • 对数复杂度 O(logN):随着数据量翻倍,算法执行时间仅轻微增加,效率下降不明显。
  • 线性复杂度 O(N):算法执行时间与数据量成正比,数据量增大时,效率线性下降。
  • 线性对数复杂度 O(NlogN):效率略低于线性复杂度,但优于平方复杂度。数据量翻倍时,效率下降速度介于线性与平方之间。
  • 平方复杂度 O(N^2):算法执行时间随数据量平方增长,数据量翻倍时,效率显著下降。
  • 立方复杂度 O(N^3):比平方复杂度更慢,数据量翻倍时,效率下降速度更快。
  • 指数复杂度 O(2^N):数据量增加时,算法执行时间呈爆炸性增长,数据量翻倍导致效率急剧下降,对于大数据集几乎不可行。

文章配图


三、复杂度的计算

1、时间复杂度计算

时间复杂度就是计算算法完成任务时,基本操作执行的次数如何随数据量变化。比如,遍历一个列表的算法,其基本操作(如访问元素)执行次数与列表长度N成正比,所以时间复杂度是O(N)。

2、空间复杂度计算

空间复杂度衡量的是算法运行时需要占用的存储空间大小。简单说,就是算法运行时 “用了多少地方” 。比如,使用一个固定大小的变量,空间复杂度为O(1);若使用了一个与数据量N相等的数组,则空间复杂度为O(N)。

3、最好、最坏、平均复杂度

  • 最好复杂度:算法在 “最顺利” 时的运行时间。
  • 最坏复杂度:算法在 “最糟糕” 时的运行时间。
  • 平均复杂度:算法在不同输入下运行时间的 “平均值” 。

四、C语言中的复杂度分析实例

1、求和函数

int sum(int arr[], int n) 
{int res = 0;for (int i = 0; i < n; i++) {res += arr[i];}return res;
}

时间复杂度O(N),因为循环n次,每次循环执行一次加法操作
空间复杂度O(1),因为额外的变量只有res和i

2、冒泡排序

void bubbleSort(int arr[], int n) 
{for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {//交换arr[j]和arr[j+1]int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}

时间复杂度O(N^2),因为有两层嵌套的循环,每层循环最多执行n次
空间复杂度O(1),因为额外的变量只有i, j和temp

3、矩阵乘法

void matrixMultiplication(int A[][2], int B[][2], int C[][2], int n) 
{for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {C[i][j] = 0;for (int k = 0; k < n; k++) {C[i][j] += A[i][k] * B[k][j];}}}
}

时间复杂度O(N^3),因为有三层嵌套的循环,每层循环最多执行n次
空间复杂度O(N^2),因为需要存储结果矩阵C

4、递归计算斐波拉契数

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

时间复杂度O(2^N),画递归栈帧的二叉树图理解
空间复杂度O(N),画递归栈帧的二叉树图理解

文章配图

注意:

  • 空间是函数进入开辟,函数退出销毁的(所以不是开辟过多少空间,空间复杂度就是多少)
  • 时间是连续的,函数栈帧的创建和销毁都需要消耗时间(因为这里返回两个函数的返回相加,所以是二叉树)

五、扩展阅读

  • 学好算法对一个程序员来说是必须的吗?如果是,至少应该学到哪种程度?
  • 学数据结构和算法一定要多刷题,多练习
  • 维基百科 - 数据结构
  • 维基百科 - 算法

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com