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

这篇具有很好参考价值的文章主要介绍了【数据结构】算法的复杂度分析:让你拥有未卜先知的能力。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度

  • 👑专栏内容:数据结构
  • ⛪个人主页:子夜的星的主页
  • 💕座右铭:日拱一卒,功不唐捐


一、前言

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

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

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

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度
可以说,学会了如何分析一个算法的复杂度,就拥有了未卜先知的能力,即在这个算法被写出来之前,就能大致评判出这个算法的好坏。

二、时间复杂度

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

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

2、大O的渐进表示法

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

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

3、常见的时间复杂度

  • O ( 1 ) O(1) O(1)

一般情况下,要算法的执行时间不随问题规模 n 的增加而增大,那么就是 O ( 1 ) O(1) O(1)的时间复杂度

void Func(int n)
{
 int count = 0;
 for (int k = 0; k < 100; ++ k)
 {
 ++count;
 }
 printf("%d\n", count);
}

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

  • O ( l o g n ) O(logn) O(logn)

类似于二分查找、幂运算都是 O ( l o g n ) O(logn) O(logn)的时间复杂度

void Func(int n)
{
 int i=1;
 while (i <= n)  
 {
   i = i * 2;
 }
}

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

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度

为什么可以忽略掉底数?
高中学过的换底公式: l o g b n = l o g b a ∗ l o g a n log_bn=log_ba*log_an logbn=logbalogan
现在假设底数不是2是3,我们可以把 l o g 3 n log_3n log3n写成 l o g 3 2 ∗ l o g 2 n log_32*log_2n log32log2n,根据前面的规矩:如果最高阶项存在且不是1,则去除与这个项目相乘的常数。 而这里的 l o g 3 2 log_32 log32是个常数,可以直接去除。所以兜兜转转,最后的时间复杂度还是 O ( l o g n ) O(logn) O(logn)

  • O ( n l o g n ) O(nlogn) O(nlogn)
void Func(int n)
{
	for (int i = 1; i <= n; i++)
	{
		int j = 1;
		while (j <= n)
		{
			j = j * 2;
		}
	}
}

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

  • O ( n ) O(n) O(n)
void Func(int n)
{
	for (int i = 1; i <= n; i++)
	{
		printf("我一共执行了n次哦!");
	}
}
  • O ( n 2 ) O(n^2) O(n2)

循环套循环,每个循环都是n次

void Func(int n)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			printf("我一共执行了n*n次哦!");
		}
	}
}
  • O ( m ∗ n ) O(m*n) O(mn)
void Func(int n,int m)
{
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			printf("看的出来我有那些不一样吗?");
		}
	}
}

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度
确实还有其他很多不同的时间复杂度,比如, O ( 2 n ) 、 O ( n ! ) O(2^n)、O(n!) O(2n)O(n!)…但是这些时间复杂度都太高了,以至于高到很多计算机都承受不了,所以比较少见。

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度
反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度

三、空间复杂度

1、定义

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

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

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

2、常见的空间复杂度

  • O ( 1 ) 型 O(1)型 O(1)

无论 n 的值如何变化,代码在执行过程中开辟的内存空间是固定的

void Func(int n)
{
	int i = 0; int sum = 0;
	for (i = 1; i < n; i++)
	{
		sum = sum + i;
	}
}

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

  • O ( n ) 型 O(n)型 O(n)

随着n的值的增大,开辟的空间也逐渐增大

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

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

  • O ( n 2 ) 型 O(n^2)型 O(n2)
  int** fun(int n) {
    int ** s = (int **)malloc(n * sizeof(int *));
    while(n--)
      s[n] = (int *)malloc(n * sizeof(int));
    return s;
  }

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

反幂法 计算复杂度,趣学数据结构,算法,数据结构,时间复杂度,空间复杂度文章来源地址https://www.toymoban.com/news/detail-779278.html

到了这里,关于【数据结构】算法的复杂度分析:让你拥有未卜先知的能力的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法——TypeScript】算法的复杂度分析、 数组和链表的对比

    什么是算法复杂度(现实案例)? ❤️‍🔥 前面已经解释了什么是算法? 其实就是解决问题的一系列步骤操作、逻辑。 ✅ 对于同一个问题,我们往往有很多种解决思路和方法,也就是可以采用不同的算法。 举个例子(现实例子):在一个庞大的图书馆中,我们需要找一本书

    2024年02月14日
    浏览(53)
  • 扎实打牢数据结构算法根基,从此不怕算法面试系列之007 week01 02-07 简单的复杂度分析

    复杂度分析本身是非常理论化的一个内容,在计算机科学中,有一个专门的学科叫做—— 计算复杂性理论 。 很多童鞋看过《算法导论》,这本书的内容很多很强调算法导论。 但是实际上,对于普通程序员来说, 不需要 过度强调理论化的内容 。因为工作中更多面对的是实际

    2023年04月19日
    浏览(59)
  • 数据结构:算法(特性,时间复杂度,空间复杂度)

    算法(Algorithm)是对 特定问题求解步骤 的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作。 一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成。 算法必须是有穷的,而程序可以是无穷的 算法中每条指令必须有确切的含义,对于

    2024年02月06日
    浏览(57)
  • 【数据结构和算法】时间复杂度和空间复杂度

    目录   一、前言 二、时间复杂度 2.1时间复杂度表示形式 2.1.1规则: 3.1如何计算时间复杂度 3.1.1线性阶 3.1.2平方阶 3.1.3对数阶 常见的时间复杂度排序: 三、空间复杂度 3.1Java的基本类型内存占用 数据结构和算法是程序的灵魂,这是某位程序员大佬所言,学习了这门,我们便可

    2023年04月09日
    浏览(48)
  • 数据结构与算法-时间复杂度与空间复杂度

    数据结构是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 算法就是定义良好的计算过程,他取一个或一组的值为输入,并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤,用来将输入数据转化成输出结果。 算法在

    2024年02月07日
    浏览(49)
  • 数据结构与算法—时间复杂度和空间复杂度

    目录 1、什么是数据结构? 2、什么是算法? 3、算法的复杂度 4、时间复杂度 (1) 时间复杂度的概念:  (2) 大O的渐进表示法:  六个例题: (3) 时间复杂度对比:  三个例题:  OJ题分析时间复杂度 5、空间复杂度 (1)常见复杂度对比  (2)OJ题分析空间复杂度 小结 数据结构 (D

    2024年02月07日
    浏览(92)
  • 算法的时间复杂度和空间复杂度(数据结构)

    目录 1、算法效率 1如何衡量一个算法的好坏 2算法的复杂度 2、时间复杂度 1时间复杂度的概念 2大O的渐进表示法 2时间复杂度计算例题 1、计算Func2的时间复杂度 2、计算Func3的时间复杂度 3、计算Func4的时间复杂度 4、计算strchr的时间复杂度 5、计算BubbleSort的时间复杂度 6、计算

    2024年02月03日
    浏览(68)
  • 数据结构--算法的时间复杂度和空间复杂度

    算法效率是指 算法在计算机上运行时所消耗的时间和资源 。这是衡量算法执行速度和资源利用情况的重要指标。 例子: 这是一个斐波那契函数,用的是递归的计算方法,每次创建函数就会在栈区开辟一块空间,递归次数越多,开辟空间越多; 所以, 代码的简洁说明不了算

    2024年02月15日
    浏览(50)
  • 【数据结构与算法篇】时间复杂度与空间复杂度

       目录 一、数据结构和算法 1.什么是数据结构?  2.什么是算法? 3.数据结构和算法的重要性 二、算法的时间复杂度和空间复杂度 1.算法效率 2.算法的复杂度 3.复杂度在校招中的考察 4.时间复杂度 5.空间复杂度  6.常见复杂度对比 7.复杂度的OJ练习   👻内容专栏:《数据结

    2023年04月24日
    浏览(67)
  • 学习数据结构:算法的时间复杂度和空间复杂度

    衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外空间。 算法的时间复杂度 算法中的基本操作的执行次数,为算法的时间复杂度。 算法的

    2024年04月11日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包