数据结构学习之路--算法的时间复杂度与空间复杂度(精讲)

这篇具有很好参考价值的文章主要介绍了数据结构学习之路--算法的时间复杂度与空间复杂度(精讲)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

     嗨嗨大家!本期带来的内容是:算法的时间复杂度与空间复杂度。


目录

前言

一、算法效率

算法效率的衡量标准

二、时间复杂度

1 时间复杂度的定义

2 求解时间复杂度的步骤

2.1 找出算法中的基本语句: 

2.2计算基本语句执行次数的数量级:

2.3大O阶的渐进表示法:

3 代码示例与解析

3.1 计算1+2+3+4+...+100的和

(1)常规算法

(2)高斯算法

3.2 求两个n 阶方阵C=A*B的乘积 

3.3 分析下面代码的时间复杂度

(1)代码1

(2)代码2 

4 情况的判断 

 三、空间复杂度


前言

   时间复杂度是衡量一个算法的好坏,也是算法题的重中之重。但是很多初学者认为时间复杂度不好理解,对于其复杂程序的估算无从下手。那么本篇文章将从简单到复杂来介绍时间复杂度的计算方法,希望给迷茫的你们指明一条前进的方向。

一、算法效率

算法效率的衡量标准

   当给定一个算法时,我们要做两项分析。第一项是以数学的角度来证明算法的正确性,这一步主要用到形式化证明的方法及相关的推理模式,例如数学归纳法。然而在证明算法正确的基础上,便需要第二项的内容了。第二项就要分析算法的时间复杂度与空间复杂度,算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。

二、时间复杂度

1 时间复杂度的定义

   在计算机科学中,算法的时间复杂度是一个函数。一个算法执行所耗费的时间,从理论上说,是不能被算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是若每个算法都需要上机测试,会很麻烦,所以才有了时间复杂度的分析方式。

   一个算法中的语句执行次数称为语句(时间)频度,记作T(n) ,这里的n是问题的规模。当n不断变化时,时间频度T(n) 也会不断变化。那我们就会想:它变化时呈现的规律是怎样的?为此,来引入时间复杂度的概念。

   时间(计算)复杂度又称时间复杂性,它是一个算法运行时间的相对度量。一个算法的运行时间长短,大致等于执行简单操作(赋值、比较、计算、转向、返回、输入和输出)所需要的时间与算法中进行简单操作次数的乘积

2 求解时间复杂度的步骤

2.1 找出算法中的基本语句: 

   一般来说,算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。

2.2计算基本语句执行次数的数量级:

   这里仅计算基本语句执行次数的数量级,意味着只要保留基本语句执行次数的函数中的最高次幂正确即可,从而可以忽略所有低次幂和最高次幂的系数,进而能够简化算法分析。通常情况下,算法的基本操作重复执行的次数是问题规模n 的某个函数,用T(n) 表示

2.3大O阶的渐进表示法:

   大O:用来描述函数渐进行为的数学符号。

   如果有某个辅助函数f(n) ,使得在n趋近于无穷大时,T(n) /f(n) 的极限值不等于0 的常数,则称f(n) 是T(n) 的同数量级函数。记作T(n)=O(f(n))。

其实,简单来说,就是保留求出次数的最高次幂,并把系数去掉。如:T(n)=2n^2+n+1=O(n^2)。

为方便大家理解,用代码举例:

#include<stdio.h> 	  
int main()  
{  
   int i, j, x = 0, sum = 0, n = 100;  //执行1次//  
    for( i = 1; i <= n; i++)           //执行n+1次//  
	 {  
	   sum = sum + i;                  // 执行n次 //     
           for( j = 1; j <= n; j++)    // 执行n*(n+1)次//  
	       {  
	          x++;                     //执行n*n次//  
            	  sum = sum + x;       //执行n*n次//  
              }  
	 }  
	    printf("%d", sum);             //执行1次//  
}  

注:因为for语句会加到n+1,会执行n+1次,而它的函数体在 i==n+1 时不满足判断条件,所以只执行n次

结论:要看清题目中问的是for语句的执行次数,还是它的循环体执行的次数。 

下面我们根据以上的代码,来详细推导“大O阶” 的步骤。

  • 第一步:用常数 1 取代运行时间中的所有加法常数

则上面的算式变为:执行总次数 =3n^2 + 3n + 1,(直接相加的话,应该是T(n) = 1 + n+1 + n +n*(n+1) + n*n + n*n + 1 = 3n^2 + 3n + 3。现在用常数 1 取代运行时间中的所有加法常数,就是把T(n) =3n^2 + 3n + 3中的最后一个3改为1. 就得到了 T(n) = 3n^2 + 3n + 1)

  • 第二步:在修改后的运行次数函数中,只保留最高阶项

这里的最高阶是 n 的二次方,所以算式变为:执行总次数 = 3n^2

  • 第三步:如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数

这里 n 的二次方不是 1 所以要去除这个项的相乘常数,算式变为:执行总次数 = n^2,因此最后我们得到上面那段代码的算法时间复杂度表示为: O( n^2 )。

下面把常见的算法时间复杂度以及它们在效率上的高低顺序记录在这里,使大家对算法的效率有个直观的认识。 

O(1) 常数阶< O(logn) 对数阶< O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < { O(2^n) < O(n!)< O(n^n) }

注:最后用大括号的三项即便是在n 的规模很小的情况下依然要耗费大量的时间,算法的时间复杂度大到无法想象,基本上是不可用的状态。

看到这里,时间复杂度的相关原理就介绍完了。我们通过几个代码示例来具体分析时间复杂度的计算过程:

3 代码示例与解析

3.1 计算1+2+3+4+...+100的和

(1)常规算法
#include<stdio.h>
int main()  
{  
    int i, sum = 0, n = 100;    //执行1次//  
    for( i = 1; i <= n; i++)    //执行n+1次//  
    {  
        sum = sum + i;          //执行n次//  
        //printf("%d\n", sum);  
    }  
    printf("%d", sum);          //执行1次//  
} 

 从附加的注释可以看到各个代码分别执行了多少次。那么这写代码语句执行次数的总和就可以理解为是该算法计算出结果所需要的时间。

该算法所用的时间(算法语句执行的总次数)为: 1 + ( n + 1 ) + n + 1 = 2n + 3。

而当 n 不断增大,比如我们这次所要计算的不是 1 + 2 + 3 + 4 +... + 100 = ? 而是 1 + 2 + 3 + 4 + ... + n = ?其中 n 是一个十分大的数字,那么上述算法的执行总次数(所需时间)会随着 n 的增大而增加,但是在 for 循环以外的语句并不受n 的规模影响(永远都只执行一次)。所以我们可以将上述算法的执行总次数简单的记做: 2n ;又因为系数2可以忽略不记,则最终的结果即为n。

这样我们就得到了我们设计的算法的时间复杂度,我们把它记作: O(n)

(2)高斯算法
#include<stdio.h> 	  
int main()  
{  
	int sum = 0, n = 100;   //执行1次//  
	sum = (1 + n) * n/2;    //执行1次//  
	printf("%d", sum);      //执行1次//  
}  

我们学到这里不难看出这个算法的时间复杂度: O(3),但一般记作 O(1)。

结论:从算法的效率上看,O(1) < O(n) ,所以高斯的算法更快,效率更高。 

3.2 求两个n 阶方阵C=A*B的乘积 

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

 该算法所有语句的频度之和为:T(n) = 2n^3+3n^2+2n+1;

 利用大O表示法,该算法的时间复杂度为O(n^3)

3.3 分析下面代码的时间复杂度

(1)代码1
int i,j, n = 100;		
for(i = 0; i < n; i++)
{
	for(j = i; j < n; j++) //j = i而不是0//
    {
		  //时间复杂度为O(1)的程序步骤序列//

	}
}

在该程序中,当 i= 0时,内循环执行了n次,当 i =1时,执行了n-1次,……当i =n-1时,执行了1次。所以总的执行次数为:n+(n-1)+(n-2)+…+ 1= n(n+1)/2= O(n^2)。

(2)代码2 
void test(int arr[], int n)  
{  
	int i, j, k;  
	for (i=0; i<n-1; i++)  
	{  
		k = i;  
		for (j=i+1; j<n; j++)  
		{  
			if (arr[k] > arr[j])  
			{  
 			    k = j;  
			}  
		}  
  		x = arr[i];  
	    arr[i] = arr[k];  
	    arr[k] = x;  
	}  
}  

其中,算法的基本语句是:

if(arr[k]>arr[j]
{
    k=j;
}

这里便可以知道,时间复杂度为O(1)。 执行次数为:n-1 + n-2 + ... + n*(n-1)/2 = O(n^2)。

4 情况的判断 

有些算法的时间复杂度存在最好、平均最坏情况:(时间复杂度取最坏情况

  •  最坏情况:任意输入规模的最大运行次数(上界)
  •  平均情况:任意输入规模的期望运行次数
  •  最好情况:任意输入规模的最小运行次数(下界)

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

  • 最好情况:1次找到
  • 最坏情况:N次找到
  • 平均情况:N/2次找到

例:我们就下面代码进行分析

//计算strchr的时间复杂度
int main()
{
   const char* strchr(const char* str,int character);
   return 0;
}

我们根据该函数原理进行分析: 

strchr函数的作用是在一个字符串中找到目标字符在该字符串中第一次出现的位置,并返回该位置;

最好情况:1次找到(目标字符就在字符串的第一个元素);

最坏情况:N次找到(目标字符在字符串的末尾);

平均情况:N/2次找到。

因此strchr 的时间复杂度为O(N) 。

 三、空间复杂度

   类似于时间复杂度的讨论,一个算法的空间复杂度S(n) 定义为该算法所耗费的存储空间,它也是问题规模n 的函数。渐近空间复杂度也常常简称为空间复杂度。算法空间复杂度的计算公式记作:S(n)=O(f(n)),其中,n 为问题的规模,f(n) 为语句关于n 所占存储空间的函数。

   空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n 的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n 的对数成正比时,可表示为O(log2n);当一个算法的空间复杂度与n 成线性比例关系时,可表示为O(n)。

   通常, 我们都使用“时间复杂度”来指运行时间的需求,使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,通常都是指时间复杂度


    本期分享已经接近尾声,那么大家对“复杂度”是否有了新的认识呢?如果这篇文章对你有所帮助,记得给博主一个三连哈~你们的支持是我创作的最大动力!前路漫漫,勿焦灼,勿烦躁。我们要有坚如磐石的信仰,脚下才有行稳致远的力量!诸君加油,不负自己!

数据结构学习之路--算法的时间复杂度与空间复杂度(精讲),数据结构,学习文章来源地址https://www.toymoban.com/news/detail-845611.html

到了这里,关于数据结构学习之路--算法的时间复杂度与空间复杂度(精讲)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构:常见算法的时间复杂度汇总

    目录 顺序表 链表 二叉树 图(V是顶点个数,E是边的条数) 1.存储空间: 2.BFS和DFS的时间复杂度 3.最小生成树时间复杂度 4.最短路径时间复杂度 查找的平均查找长度(ASL)  排序 算法操作 时间复杂度 空间复杂度 描述 插入 O(n) 需要移动元素,移动结点的平均次数n/2 删除

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

    目录 1.什么是算法? 1.1算法的复杂度 2.算法的时间复杂度 2.1 时间复杂度的概念 计算Func1中++count语句总共执行了多少次 2.2 大O的渐进表示法 2.3常见时间复杂度计算举例  实例1:执行2N+10次 实例2:执行M+N次 实例3:执行了100000000次 实例4:计算strchr的时间复杂度 实例5:计算BubbleSor

    2024年02月13日
    浏览(41)
  • 数据结构:算法(特性,时间复杂度,空间复杂度)

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

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

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

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

    目录   一、前言 二、时间复杂度 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)
  • 数据结构--算法的时间复杂度和空间复杂度

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

    2024年02月15日
    浏览(49)
  • [数据结构-C语言] 算法的时间复杂度

    目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 3、常见时间复杂度计算举例 3.1 冒泡排序 3.2 二分查找 3.3 阶乘递归 3.4 斐波那契数列 1.算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此 衡量一个算法的

    2024年02月02日
    浏览(48)
  • 数据结构与算法(Java版) | 详解算法的时间复杂度

    下面我们用一个问题来引出算法的时间复杂度这一概念。 该问题是,怎么去衡量一个程序(或者算法)的执行时间呢?就拿我们刚刚讲的排序算法来说,排序算法这么多,你又如何知晓哪一个排序算法执行的时间谁长谁短呢? 要想搞清楚该问题,那我们就不得不知道度量一

    2024年02月05日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包